兩個鏈表第一個公共結點，表第一個結點

兩個鏈表第一個公共結點，表第一個結點

題目：輸入兩個鏈表，找出它們的第一個公共節點。鏈表的定義如下：

struct ListNode

{

int m_nValue;

ListNode *m_pNext;



};

思路1：采用蠻力的方法：在第一個鏈表上順序遍歷每個節點，每遍歷到一個節點的時候，在第二個鏈表上順序遍歷每個節點。如果第二個鏈表上的節點和第一個鏈表上的節點一樣，就說明兩個鏈表在節點上重合，於是就找到了公共的節點。而通常蠻力並不是好的方法。

思路2:首先遍歷兩個鏈表得到它們的長度，就能知道哪個鏈表比較長，以及長的鏈表比短的鏈表多幾個節點。在第二次遍歷的時候，先在較長的節點上走若干步，接著同時在兩個鏈表上遍歷，找到的第一個相同的節點就是它們的公共的節點。

  1 #include "stdafx.h"
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 struct ListNode
  5  {
  6      int             m_nValue;
  7      ListNode*       m_pNext;
  8  };
  9 
 10  ListNode* CreateListNode(int value)
 11  {
 12      ListNode* pNode = new ListNode();
 13      pNode->m_nValue = value;
 14      pNode->m_pNext = NULL;
 15 
 16      return pNode;
 17  }
 18 
 19  void ConnectListNodes(ListNode* pCurrent, ListNode* pNext)
 20  {
 21      if(pCurrent == NULL)
 22      {
 23          printf("Error to connect two nodes.\n");
 24          exit(1);
 25      }
 26 
 27      pCurrent->m_pNext = pNext;
 28  }
 29 
 30  void PrintListNode(ListNode* pNode)
 31  {
 32      if(pNode == NULL)
 33      {
 34          printf("The node is NULL\n");
 35      }
 36      else
 37      {
 38          printf("The key in node is %d.\n", pNode->m_nValue);
 39      }
 40  }
 41 
 42  void PrintList(ListNode* pHead)
 43  {
 44      printf("PrintList starts.\n");
 45 
 46      ListNode* pNode = pHead;
 47      while(pNode != NULL)
 48      {
 49          printf("%d\t", pNode->m_nValue);
 50          pNode = pNode->m_pNext;
 51      }
 52 
 53      printf("\nPrintList end.\n");
 54  }
 55 
 56 void DestroyList(ListNode* pHead)
 57 {
 58     ListNode* pNode = pHead;
 59     while(pNode != NULL)
 60     {
 61         pHead = pHead->m_pNext;
 62         delete pNode;
 63         pNode = pHead;
 64     }
 65 }
 66 
 67 unsigned int GetListLength(ListNode* pHead);
 68 
 69 ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2)
 70 {
 71     // 得到兩個鏈表的長度
 72     unsigned int nLength1 = GetListLength(pHead1);
 73     unsigned int nLength2 = GetListLength(pHead2);
 74     int nLengthDif = nLength1 - nLength2;
 75  
 76     ListNode* pListHeadLong = pHead1;
 77     ListNode* pListHeadShort = pHead2;
 78     if(nLength2 > nLength1)
 79     {
 80         pListHeadLong = pHead2;
 81         pListHeadShort = pHead1;
 82         nLengthDif = nLength2 - nLength1;
 83     }
 84  
 85     // 先在長鏈表上走幾步，再同時在兩個鏈表上遍歷
 86     for(int i = 0; i < nLengthDif; ++ i)
 87         pListHeadLong = pListHeadLong->m_pNext;
 88  
 89     while((pListHeadLong != NULL) && 
 90         (pListHeadShort != NULL) &&
 91         (pListHeadLong != pListHeadShort))
 92     {
 93         pListHeadLong = pListHeadLong->m_pNext;
 94         pListHeadShort = pListHeadShort->m_pNext;
 95     }
 96  
 97     // 得到第一個公共結點
 98     ListNode* pFisrtCommonNode = pListHeadLong;
 99  
100     return pFisrtCommonNode;
101 }
102 
103 unsigned int GetListLength(ListNode* pHead)
104 {
105     unsigned int nLength = 0;
106     ListNode* pNode = pHead;
107     while(pNode != NULL)
108     {
109         ++ nLength;
110         pNode = pNode->m_pNext;
111     }
112  
113     return nLength;
114 }
115 
116 // 第一個公共結點在鏈表中間
117 // 1 - 2 - 3 \
118 //            6 - 7
119 //     4 - 5 /
120 int main()
121 {
122     ListNode* pNode1 = CreateListNode(1);
123     ListNode* pNode2 = CreateListNode(2);
124     ListNode* pNode3 = CreateListNode(3);
125     ListNode* pNode4 = CreateListNode(4);
126     ListNode* pNode5 = CreateListNode(5);
127     ListNode* pNode6 = CreateListNode(6);
128     ListNode* pNode7 = CreateListNode(7);
129 
130     ConnectListNodes(pNode1, pNode2);
131     ConnectListNodes(pNode2, pNode3);
132     ConnectListNodes(pNode3, pNode6);
133     ConnectListNodes(pNode4, pNode5);
134     ConnectListNodes(pNode5, pNode6);
135     ConnectListNodes(pNode6, pNode7);
136 
137     ListNode* pResult = FindFirstCommonNode(pNode1, pNode4);
138     printf("%d\n",pResult->m_nValue);
139     
140     DestroyNode(pNode1);
141     DestroyNode(pNode2);
142     DestroyNode(pNode3);
143     DestroyNode(pNode4);
144     DestroyNode(pNode5);
145     DestroyNode(pNode6);
146     DestroyNode(pNode7);
147         
148     return 0;
149 }