判断两个链表是否相交，若相交，求交点。_判断两个单向链表是否相交,如果相交,求出交点

首先我们来看一下单链表：

第一种情况：两个链表均不带环 

判断两个不带环的链表是否相交，如果两个链表相交的话可如下图所示：

判断是否相交：由上图可知，如果两个不带环链表相交的话这两个不带坏链表的尾节点地址一定相同，所以我们只要各自遍历两个链表，判断其尾节点地址是否相同，如果相同则相交，否则不相交。

typedef struct SListNode
{
	DataType data;
	struct SListNode *pNext;
} SListNode;
 
 
//判断两个链表是否相交
int IsSListCross(SListNode *pHead1, SListNode *pHead2)
{
	SListNode *pTail1 = pHead1;
	SListNode *pTail2 = pHead2;
	assert(pHead1);
	assert(pHead2);
	if (NULL == pHead1 || NULL == pHead2)
		return 0;
	while (pTail1->pNext)
		pTail1 = pTail1->pNext;
	while (pTail2->pNext)
		pTail2 = pTail2->pNext;
	return pTail1 == pTail2;
}

 相交求交点（两种方法）：

法一：因为两个不带环链表相交，所以让第一个链表的尾节点的pNext指向第二个链表的第一个节点，构成一个带环的单链表，然后求该带环单链表环的入口点即为两个链表的交点。那么如何求一个带环链表的入口点呢？

我们可以利用2个指针，一个快指针（一次走两步），一个慢指针（一次走一步）。因为该链表带环，所以快慢指针一旦入环，总会相遇，记录下此时的相遇点，然后让链表的第一个节点和此相遇点同时往后走，它们相等时的节点即为带环链表的入口点。

//求交点（法一）
/*
第一步：两个链表构成环：第一个链表的尾节点指向第二个链表的头节点
第二步：求此环的入口点
*/
SListNode *GetCrossNode0(SListNode *pHead1, SListNode *pHead2)
{
	SListNode *pCur = pHead1;
	SListNode *pFast = pHead1;
	SListNode *pSlow = pHead2;
	if (pHead1 == NULL || pHead2 == NULL)
	{
		return NULL;
	}
	while (pCur->pNext != NULL)
	{
		pCur = pCur->pNext;
	}
	pCur->pNext = pHead2;   //构成带环链表
	pCur = pHead1;
	while (pFast&&pFast->pNext)
	{
		pFast = pFast->pNext->pNext;
		pSlow = pSlow->pNext;
		if (pSlow == pFast)
		{
			break;
		}
	}
	while (pCur != pSlow)
	{
		pCur = pCur->pNext;
		pSlow = pSlow->pNext;
	}
	return pCur;
}
 

 法二：因为两个相交链表从交点往后的节点地址都是相同的，只要我们首先求出两个不带环的链表的长度size1和size2，然后让长的链表先走（size1 - size2）步，再让两个链表同时往后走，两个链表第一次节点地址相同的点即为交点。

//求交点，链表不带环 （法二）
/*
第一步：求2个链表的长度
第二步：长的先走长度的差值步
第三步：同时走，第一次节点地址相同的地方就是交点
*/
SListNode *GetCrossNode(SListNode *pHead1, SListNode *pHead2)
{
	int size1 = 0, size2 = 0;
	int gap = 0;
	SListNode *pCur1 = pHead1;
	SListNode *pCur2 = pHead2;
	if (!IsSListCross(pHead1, pHead2))  //链表不相交
		return NULL;
	while (pCur1)   //求第一个链表的长度
	{
		size1++;
		pCur1 = pCur1->pNext;
	}
	while (pCur2)  //求第二个链表的长度
	{
		size2++;
		pCur2 = pCur2->pNext;
	}
	gap = size1 - size2;   //求两个链表的长度差
	pCur1 = pHead1;
	pCur2 = pHead2;
	if (gap > 0)  //如果第一个链表较长，则先走gap步
	{
		while (gap--)
		{
			pCur1 = pCur1->pNext;
		}
	}
	else    //如果第二个链表较长，则先走gap步
	{
		while (gap++)
		{
			pCur2 = pCur2->pNext;
		}
	}
	while (pCur1 != pCur2)    //两个链表同时往后走
	{
		pCur1 = pCur1->pNext;
		pCur2 = pCur2->pNext;
	}
	return pCur1;
}

第二种情况：两个链表均带环

如果两个均带环链表相交的话，一种情况是交点在环外：

此时由于交点在环外，只要我们将环的入口点断开，便成了两个不带环链表求交点，可用第一种情况中任意一种方法求解。

上边第一种情况方法一里边已经给出了求环的相遇点及入口点的方法，这里只单独给出相关代码。

 

//判断单链表是否带环(求相遇点)
SListNode *IsSListCircle(SListNode *pHead)
{
	SListNode *pFast = pHead;
	SListNode *pSlow = pHead;
	while (pFast && pFast->pNext)
	{
		pFast = pFast->pNext->pNext;
		pSlow = pSlow->pNext;
		if (pSlow == pFast)
			return pSlow;
	}
	return NULL;
}
 
 
//若带环，求入口点
SListNode *GetCircleEnter(SListNode *pHead)
{
	SListNode *pCur1 = pHead;
	SListNode *pCur2 = IsSListCircle(pHead);
	if (NULL == pCur1 || NULL == pCur2)
		return NULL;
	while (pCur1 != pCur2)
	{
		pCur1 = pCur1->pNext;
		pCur2 = pCur2->pNext;
	}
	return pCur2;
}

另一种情况如下图所示，此时不存在所谓的交点。

  

第三种情况：一个链表带环，一个链表不带环，此时两个链表必然不存在交点。