程序员面试题精选100题（35）-两链表的第一个公共结点[数据结构]

//         nodes, return NULL

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

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