兩個鏈表第一個公共結點

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

struct ListNode

{

int m_nValue;

ListNode *m_pNext;

};

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

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

#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>
struct ListNode
{
int m_nValue;
ListNode* m_pNext;
};

ListNode* CreateListNode(int value)
{
ListNode* pNode = new ListNode();
pNode->m_nValue = value;
pNode->m_pNext = NULL;

return pNode;
}

void ConnectListNodes(ListNode* pCurrent, ListNode* pNext)
{
if(pCurrent == NULL)
{
printf("Error to connect two nodes.\n");
exit(1);
}

pCurrent->m_pNext = pNext;
}

void PrintListNode(ListNode* pNode)
{
if(pNode == NULL)
{
printf("The node is NULL\n");
}
else
{
printf("The key in node is %d.\n", pNode->m_nValue);
}
}

void PrintList(ListNode* pHead)
{
printf("PrintList starts.\n");

ListNode* pNode = pHead;
while(pNode != NULL)
{
printf("%d\t", pNode->m_nValue);
pNode = pNode->m_pNext;
}

printf("\nPrintList end.\n");
}

void DestroyList(ListNode* pHead)
{
ListNode* pNode = pHead;
while(pNode != NULL)
{
pHead = pHead->m_pNext;
delete pNode;
pNode = pHead;
}
}

unsigned int GetListLength(ListNode* pHead);

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 > nLength1)
{
pListHeadLong = pHead2;
pListHeadShort = pHead1;
nLengthDif = nLength2 - nLength1;
}

// 先在長鏈表上走幾步，再同時在兩個鏈表上遍歷
for(int i = 0; i < nLengthDif; ++ i)
pListHeadLong = pListHeadLong->m_pNext;

while((pListHeadLong != NULL) &&
(pListHeadShort != NULL) &&
(pListHeadLong != pListHeadShort))
{
pListHeadLong = pListHeadLong->m_pNext;
pListHeadShort = pListHeadShort->m_pNext;
}

// 得到第一個公共結點
ListNode* pFisrtCommonNode = pListHeadLong;

return pFisrtCommonNode;
}

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

return nLength;
}

// 第一個公共結點在鏈表中間
// 1 - 2 - 3 \
// 6 - 7
// 4 - 5 /
int main()
{
ListNode* pNode1 = CreateListNode(1);
ListNode* pNode2 = CreateListNode(2);
ListNode* pNode3 = CreateListNode(3);
ListNode* pNode4 = CreateListNode(4);
ListNode* pNode5 = CreateListNode(5);
ListNode* pNode6 = CreateListNode(6);
ListNode* pNode7 = CreateListNode(7);

ConnectListNodes(pNode1, pNode2);
ConnectListNodes(pNode2, pNode3);
ConnectListNodes(pNode3, pNode6);
ConnectListNodes(pNode4, pNode5);
ConnectListNodes(pNode5, pNode6);
ConnectListNodes(pNode6, pNode7);

ListNode* pResult = FindFirstCommonNode(pNode1, pNode4);
printf("%d\n",pResult->m_nValue);

DestroyNode(pNode1);
DestroyNode(pNode2);
DestroyNode(pNode3);
DestroyNode(pNode4);
DestroyNode(pNode5);
DestroyNode(pNode6);
DestroyNode(pNode7);

return 0;
}