offer_52

//面试题52：两个链表的第一个公共节点
ListNode* FindFirstCommonNode(ListNode* pHead1,ListNode* pHead2)
{
  unsigned int nLength1=GetListLength(pHead1);
  unsigned int nLength2=GetListLength(pHead2);
  int nLengthDif=nLength1-nLength2;
  
  ListNode* pListHeadLong=pHead1;
  ListNode* pListHeadShort=pHead2;
  if(nLength2>nLengeth1){
    nLengthDif=nLength2-nLength1;
    pListHeadLong=pHead2;
    pListHeadShort=pHead1;
  }
  
  //现在长链表上走几步，再同时在两个链表上遍历
  for(int i=0;i<nLengthDif;++i)
    pListHeadLong=pListHeadLong->m_pNext;
  
  while((pListHeadLong!=nullptr)&&(pListHeadShort!=nullptr)&&(pListHeadLong!=pListHeadShort)){
    pListHeadLong=pListHeadLong->m_pNext;
    pListHeadShort=pListHeadShort->m_pNext;
  }
  //得到第一个公共节点
  ListNode* pFirstCommonNode=pListHeadLong;
  
  return pFirstCommonNode；
}

unsigned int GetListLength(ListNode* pHead)
{
  unsigned int nLength=0;
  ListNode* pNode=pHead;
  while(pNode!=nullptr){
    ++nLength;
    pNode=pNode->m_pNext;
  }
  return nLength;
}