尋找兩個相交鏈表的第一個公共節點

// 尋找兩個鏈表的第一個公共節點.cpp : Defines the entry point for the console application.
//
/*
1.最簡單的方法就是先順序訪問其中一個鏈表，在每訪問一個節點時，都對另外一個鏈表進行遍歷，看節點是否相等
  直到找到一個相等的節點位置，如果鏈表長度分別是m,n 則時間復雜度為O(mn)
2.我們可以知道如果兩個鏈表有公共節點，那麼該公共節點之後的所有節點都是兩個鏈表所共有的，所以長度一定也是
相等的，如果兩個鏈表的總長度是相等的，那麼我們對兩個鏈表進行遍歷，則一定同時到達第一個公共節點。但是鏈表
的長度實際上不一定相同，所以我們只需要計算出兩個鏈表的長度之差n，然後讓長的那個鏈表先移動n步，短的鏈表再
開始向後遍歷，這樣他們一定同時到達第一個公共節點，我們只需要在向後移動的時候比較兩個鏈表的節點是否相等就
可以獲得第一個公共節點。時間復雜度是O(m+n)
*/
#include "stdafx.h"
struct ListNode
{
	int m_data;
	ListNode *m_pNext;
};
unsigned int ListLength(ListNode* pHead)
{
	unsigned int nLength = 0;
	ListNode* pNode = pHead;
	while(pNode != NULL)
	{
		++ nLength;
		pNode = pNode->m_pNext;
	}

	return nLength;
}
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
	ListNode *pFisrtCommonNode = NULL;
	if(pListHeadLong == pListHeadShort)
		pFisrtCommonNode = pListHeadLong;
	return pFisrtCommonNode;
}