学步园

题目来自编程之美

题目:判断两个无环相交的两个链表的交点

思路:使用类似指针追赶的方法得到,具体见单链表面试题

代码

ListNode* FindCrossingNode(ListNode* pFirstHead,ListNode* pSecHead)
{
	assert(pFirstHead != NULL && pSecHead);
	int nLenOfFirst = 0;
	int nLenOfSec = 0;
	ListNode* pCurFirst = pFirstHead;
	ListNode* pCurSec = pSecHead;

	//获得第一个链表的长度
	while (pCurFirst)
	{
		nLenOfFirst++;
		pCurFirst = pCurFirst->m_pNext;
	}
	//获得第二个链表的长度
	while (pCurSec)
	{
		nLenOfSec++;
		pCurSec = pCurSec->m_pNext;
	}
	//利用指针追赶的方法求交点
	pCurFirst = pFirstHead;
	pCurSec = pSecHead;
	while (nLenOfFirst > nLenOfSec)
	{
		pCurFirst = pCurFirst->m_pNext;
		nLenOfSec++;
	}
	while (nLenOfSec > nLenOfFirst)
	{
		pCurSec = pCurSec->m_pNext;
		nLenOfFirst++;
	}
	while (pCurFirst != pCurSec)
	{
		pCurFirst = pCurFirst->m_pNext;
		pCurSec = pCurSec->m_pNext;
	}
	return pCurFirst;
}

测试代码

#include <iostream>
#include <assert.h>
using namespace std;

struct ListNode
{
	int m_Data;
	ListNode* m_pNext;
};

ListNode* FindCrossingNode(ListNode* pFirstHead,ListNode* pSecHead)
{
	assert(pFirstHead != NULL && pSecHead);
	int nLenOfFirst = 0;
	int nLenOfSec = 0;
	ListNode* pCurFirst = pFirstHead;
	ListNode* pCurSec = pSecHead;

	//获得第一个链表的长度
	while (pCurFirst)
	{
		nLenOfFirst++;
		pCurFirst = pCurFirst->m_pNext;
	}
	//获得第二个链表的长度
	while (pCurSec)
	{
		nLenOfSec++;
		pCurSec = pCurSec->m_pNext;
	}
	//利用指针追赶的方法求交点
	pCurFirst = pFirstHead;
	pCurSec = pSecHead;
	while (nLenOfFirst > nLenOfSec)
	{
		pCurFirst = pCurFirst->m_pNext;
		nLenOfSec++;
	}
	while (nLenOfSec > nLenOfFirst)
	{
		pCurSec = pCurSec->m_pNext;
		nLenOfFirst++;
	}
	while (pCurFirst != pCurSec)
	{
		pCurFirst = pCurFirst->m_pNext;
		pCurSec = pCurSec->m_pNext;
	}
	return pCurFirst;
}

/*思路:判断两个单链表最后一个元素是否相等*/
bool IsCrossing(ListNode* pFirstHead,ListNode* pSecHead)
{
	assert(pFirstHead != NULL && pSecHead);
	ListNode* pCurOfFirst = pFirstHead;
	ListNode* pCurOfSec = pSecHead;
	//寻找第一个链表最后一个结点
	while (pCurOfFirst->m_pNext)
	{
		pCurOfFirst = pCurOfFirst->m_pNext;
	}
	//寻找第二个链表最后一个结点
	while (pCurOfSec->m_pNext)
	{
		pCurOfSec = pCurOfSec->m_pNext;
	}
	//判断是否相交
	if (pCurOfFirst == pCurOfSec)
	{
		return true;
	}
	else
	{
		return false;
	}
}

void CreateList(ListNode** pHead,int nLen)//头指针使用指针的指针
{
	assert(*pHead == NULL && nLen > 0);
	ListNode* pCur = NULL;
	ListNode* pNewNode = NULL;
	for (int i = 0;i < nLen;i++)
	{
		pNewNode = new ListNode;
		cin>>pNewNode->m_Data;
		pNewNode->m_pNext = NULL;

		if (*pHead == NULL)
		{
			*pHead = pNewNode;
			pCur = *pHead;
		}
		else
		{
			pCur->m_pNext = pNewNode;
			pCur = pNewNode;
		}
	}
}

/*让第一个链表的尾指针指向第二个链表的第三个元素
如果第二个链表没有第三个元素，则两个链表不相交*/
void CreateCrossingList(ListNode* pFirstHead,ListNode* pSecHead)
{
	assert(pFirstHead != NULL && pSecHead);
	ListNode* pCurOfFirst = pFirstHead;
	ListNode* pCurOfSec = pSecHead;
	//寻找第一个链表最后一个结点
	while (pCurOfFirst->m_pNext)
	{
		pCurOfFirst = pCurOfFirst->m_pNext;
	}
	//第一个链表最后一个结点指向第二链表的第三个元素
	if (pCurOfSec->m_pNext && pCurOfSec->m_pNext->m_pNext)
	{
		pCurOfFirst->m_pNext = pCurOfSec->m_pNext->m_pNext;
	}	
}



int main()
{
	int nLen = 0;
	bool bIsCrossing = false;
	ListNode* pHeadFirst = NULL;
	ListNode* pHeadSec = NULL;
	ListNode* pCrossingNode = NULL;

	//创建有环链表
	cout<<"please input node num: ";
	cin >> nLen;
	CreateList(&pHeadFirst,nLen);

	//创建有环链表
	cout<<"please input node num: ";
	cin >> nLen;
	CreateList(&pHeadSec,nLen);

	CreateCrossingList(pHeadFirst,pHeadSec);
	bIsCrossing = IsCrossing(pHeadFirst,pHeadSec);
	if (bIsCrossing)
	{
		cout<<"相交!"<<endl;
		pCrossingNode = FindCrossingNode(pHeadFirst,pHeadSec);
		cout<<"相交结点:"<<pCrossingNode->m_Data<<endl;
	}
	else
	{
		cout<<"不相交!"<<endl;
	}

	system("pause");
	return 1;
}