兩個鏈表的第一個公共節點

/********************************************************************
題目:輸入兩個鏈表，找出它們的第一個公共節點。
********************************************************************/
/*
解題思路：
先遍歷兩個鏈表得到他們的長度，就能知道哪個鏈表較長，以及長的鏈表比短的
鏈表多幾個節點。在第二次遍歷的時候，在較長的鏈表上先走若干步，接著再同
時在兩個鏈表上遍歷，找到第一個相同的節點就是他們的第一個公共節點。
*/
#include
struct ListNode
{
	int m_nValue;
	ListNode* m_pNext;
};
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* pLong = pHead1;
	ListNode* pShort = pHead2;
	
	if(nLength1 < nLength2)
	{
		pLong = pHead2;
		pShort = pHead1;
		nLengthDif = nLength2 - nLength1;
	}

	for(int i=0; im_pNext;

	while((pLong != NULL) && (pShort != NULL) && (pLong != pShort))
	{
		pLong = pLong->m_pNext;
		pShort = pShort->m_pNext;
	}
	//得到第一個公共節點
	ListNode* pFirstCommonNode = pLong;

	return pFirstCommonNode;
}
int getListLength(ListNode* pHead)
{
	if(pHead == NULL)
		return 0;

	unsigned int nLength = 0;
	ListNode* pNode = pHead;
	while(pNode != NULL)
	{
		++nLength;
		pNode = pNode->m_pNext;
	}
	return nLength;
}
ListNode* createListNode(int value)
{
	ListNode* pNode = new ListNode();
	pNode->m_nValue = value;
	pNode->m_pNext = NULL;
	return pNode;
}
void connect(ListNode* pNode1, ListNode* pNode2)
{
	if(pNode1 == NULL || pNode2 == NULL)
		return;
	pNode1->m_pNext = pNode2;
}

void test()
{
	ListNode* pNode1 = createListNode(1);
	ListNode* pNode2 = createListNode(2);
	ListNode* pNode3 = createListNode(3);
	ListNode* pNode4 = createListNode(4);
	ListNode* pNode5 = createListNode(6);
	ListNode* pNode6 = createListNode(7);

	connect(pNode1,pNode2);
	connect(pNode2,pNode3);
	connect(pNode3,pNode4);
	connect(pNode4,pNode5);
	connect(pNode5,pNode6);

	ListNode* pNode11 = createListNode(4);
	ListNode* pNode12 = createListNode(5);


	connect(pNode11,pNode12);
	connect(pNode12,pNode5);
	connect(pNode5,pNode6);

	ListNode* pFirst = findFirstCommonNode(pNode1,pNode11);	
	if(pFirst != NULL)
		printf("%d\n",pFirst->m_nValue);
}
int main()
{
	test();
	return 0;
}

時間復雜度為O(M+N)

==參考劍指offer