面试题37：两个链表的第一个公共节点

常考问题，

先要分别遍历两个链表得到它们的长度，并求出两个长度之差。在长的链表上先遍历若干次之后，再同步遍历两个链表，知道找到相同的结点，或者一直到链表结束。此时，如果第一个链表的长度为m，第二个链表的长度为n，该方法的时间复杂度为O(m+n)

 1 unsigned int GetListLength(ListNode* pHead);
 2 
 3 ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2)
 4 {
 5     // 得到两个链表的长度
 6     unsigned int nLength1 = GetListLength(pHead1);
 7     unsigned int nLength2 = GetListLength(pHead2);
 8     int nLengthDif = nLength1 - nLength2;
 9  
10     ListNode* pListHeadLong = pHead1;
11     ListNode* pListHeadShort = pHead2;
12     if(nLength2 > nLength1)
13     {
14         pListHeadLong = pHead2;
15         pListHeadShort = pHead1;
16         nLengthDif = nLength2 - nLength1;
17     }
18  
19     // 先在长链表上走几步，再同时在两个链表上遍历
20     for(int i = 0; i < nLengthDif; ++ i)
21         pListHeadLong = pListHeadLong->m_pNext;
22  
23     while((pListHeadLong != NULL) && 
24         (pListHeadShort != NULL) &&
25         (pListHeadLong != pListHeadShort))
26     {
27         pListHeadLong = pListHeadLong->m_pNext;
28         pListHeadShort = pListHeadShort->m_pNext;
29     }
30  
31     // 得到第一个公共结点
32     ListNode* pFisrtCommonNode = pListHeadLong;
33  
34     return pFisrtCommonNode;
35 }
36 
37 unsigned int GetListLength(ListNode* pHead)
38 {
39     unsigned int nLength = 0;
40     ListNode* pNode = pHead;
41     while(pNode != NULL)
42     {
43         ++ nLength;
44         pNode = pNode->m_pNext;
45     }
46  
47     return nLength;
48 }