寻找两个相交链表的第一个公共节点

// 寻找两个链表的第一个公共节点.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;
}

补充：软件开发 , C++ ,

上一个：归并排序
下一个：排序算法练习——代码汇总