找出链表的第一个公共结点

http://blog.163.com/longsu2010@yeah/blog/static/173612348201161543715107/

 

ListNode * FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2)

{

      // Get the length of two lists

      unsigned int nLength1 = ListLength(pHead1);

      unsigned int nLength2 = ListLength(pHead2);

      int nLengthDif = nLength1 - nLength2;

     // Get the longer list

      ListNode *pListHeadLong = pHead1;

      ListNode *pListHeadShort = pHead2;

      if(nLength2 > nLength1)

      {
            pListHeadLong = pHead2;

            pListHeadShort = pHead1;

            nLengthDif = nLength2 - nLength1;

      }
      // Move on the longer list

      for(int i = 0; i < nLengthDif; ++ i)

            pListHeadLong = pListHeadLong->m_pNext;
      // Move on both lists

      while((pListHeadLong != NULL) &&

            (pListHeadShort != NULL) &&

            (pListHeadLong != pListHeadShort))

      {
            pListHeadLong = pListHeadLong->m_pNext;

            pListHeadShort = pListHeadShort->m_pNext;
      }
      // Get the first common node in two lists

      ListNode *pFisrtCommonNode = NULL;

      if(pListHeadLong == pListHeadShort)

            pFisrtCommonNode = pListHeadLong;
      return pFisrtCommonNode;

}
///////////////////////////////////////////////////////////////////////

// Get the length of list with head pHead

// Input: pHead - the head of list

// Return: the length of list

///////////////////////////////////////////////////////////////////////

unsigned int ListLength(ListNode* pHead)

{
      unsigned int nLength = 0;

      ListNode* pNode = pHead;

      while(pNode != NULL)

      {
            ++ nLength;

            pNode = pNode->m_pNext;

      }


      return nLength;

}