兩個鏈表第一個公共結點

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

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;
}