链表面试题(三)：链表相交，链表带环，链表带环相交

深碍√TFBOYSˉ_ 2022-06-13 02:26 195阅读 0赞

接上一篇链表面试题博客：

11. 判断单链表是否带环？若带环，求环的长度？求环的入口点？

1）带环判断：定义两个指针，pFast、pSlow，其中两指针速度pFast = 2pSlow ,若带环总会有pFast == pSlow，并返回相遇节点，若不带环 这个指针的最后节点都为空。

2）求环的长度，定义计数器、 保存当前相遇节点、从相遇节点开始遍历，计数器计数，当再次与相遇节点相遇时 ，计数器就计有环长度。

3）求环的入口点：

![SouthEast][]  
代码：

//11. 判断单链表是否带环？若带环，求环的长度？求环的入口点？并计算每个算法的时间复
    //杂度&空间复杂度。
    //1)判断带环
    pNode CheckCircle(pNode pHead)
    {
    	//判断是否只有一个节点
    	if (pHead->next == NULL)
    	{
    		return NULL;
    	}
    	pNode pFast = pHead;
    	pNode pSlow = pHead;
    
    	while (pFast)
    	{
    		pFast = pFast->next->next;
    		pSlow = pSlow->next;
    		if (pFast == pSlow)
    			return pFast;
    	}
    	return NULL;
    }
    //2）求环的长度
    int GetCircleLength(pNode Meet)
    {
    	pNode pCur = Meet;
    	int len = 0;
    	do
    	{
    		pCur = pCur->next;
    		len++;
    	} while (pCur != Meet);
    	return len;
    }
    //3)求环的入口点 x = nl-y
    pNode GetCircleEnterNode(pNode pHead, pNode Meet)
    {
    	pNode pFast = Meet;//快的从相遇点开始走
    	pNode pSlow = pHead;
    
    	while (pFast != pSlow)
    	{
    		pSlow = pSlow->next;
    		pFast = pFast->next->next;
    	}
    	return pFast;
    }

12.判断两个链表是否相交，若相交，求交点。（假设链表不带环）

如下图，左边的情况一定没有交点

判断相交：两个链表分别遍历 若尾节点相同 则相交

![SouthEast 1][]

代码：

//12. 判断两个链表是否相交，若相交，求交点。（假设链表不带环）
    //首先判断是否相交
    int Check_Cross(pNode pHead1, pNode pHead2)
    {
    	pNode pList1 = pHead1;
    	pNode pList2 = pHead2;
    	if (pHead1 == NULL || pHead2 == NULL)
    	{
    		return 1;
    	}
    	while (pList1->next != NULL)
    	{
    		pList1 = pList1->next;
    	}
    	while (pList2 != NULL)
    	{
    		pList2 = pList2->next;
    	}
    	if (pList1 == pList2)
    		return 1;
    	return -1;
    }
    //相交，求交点
    //第一种
    pNode Get_Link_CrossNode(pNode pHead1,pNode pHead2)
    {
    	pNode pList1 = pHead1;
    	pNode pList2 = pHead2;
    
    	int len1 = GetLinkNode(pHead1);
    	int len2 = GetLinkNode(pHead2);
    	int length = len1 - len2;
    
    	if (length > 0)
    	{
    		//说明len1>len2
    		while (length--)
    		{
    			pList1 = pList1->next;
    		}
    		while (pList1 != pList2)
    		{
    			pList1 = pList1->next;
    			pList2 = pList2->next;
    		}
    	}
    	else
    	{
    		length = (- length);
    		while (length--)
    		{
    			pList2 = pList2->next;
    		}
    		while (pList1 != pList2)
    		{
    			pList1 = pList1->next;
    			pList2 = pList2->next;
    		}
    	}
    	return pList1;
    }
    //第二种：
    pNode _Get_Link_CrossNode(pNode pHead1, pNode pHead2)
    {
    	pNode pList1 = pHead1;
    	pNode pList2 = pHead2;
    
    	//遍历第一个链表到节点位置，让L1的尾节点指向L2头部构成环
    	while (pList1->next != NULL)
    	{
    		pList1 = pList1->next;
    	}
    	pList1->next = pList2;
    	//此时pHead1成为带环链表的入口点
    	return GetCircleEnterNode(pHead1, CheckCircle(pHead1));
    }

13. 判断两个链表是否相交，若相交，求交点。（假设链表可能带环）【升级版】  
具体情况分两种：

第一种：一个带环一个不带环 所以一定不会相交

![SouthEast 2][]

第二种：两个都带环、而这种情况 也有三个小分类

判断相交： 分别求出两个链表的环入口点meet1，meet2

第二种情况meet1==meet2，相交

第三种：若相交meet1不动，meet2通过遍历总会和meet1相遇，相交

否则就是第一种不相交

![SouthEast 3][]

这种一定不带环

![SouthEast 4][]

![SouthEast 5][]

代码：

//13. 判断两个链表是否相交，若相交，求交点。（假设链表可能带环）【升级版】
    //先判断L1、L2是否相交
    int _Check_Cross(pNode pHead1, pNode pHead2)
    {
    	pNode Meet1 = CheckCircle(pHead1);//环中相遇点
    	pNode Meet2 = CheckCircle(pHead2);
    
    	if ((Meet1 == NULL && Meet2 != NULL) || (Meet2 == NULL && Meet1 != NULL))
    	{
    		return -1;//一条带环一条不带
    	}
    	else//两条都带环
    	{
    		pNode pCur = Meet1;
    		do
    		{
    			pCur = pCur->next;
    			if (pCur == Meet2)
    			{
    				return 1;//相交，并且找到一个节点
    			}
    		} while (Meet1 != pCur);
    	}
    	return -1;// 两个带环的链表不相交
    }
    //求两个相交带环链表的节点(有两个相交节点)
    //第一种情况 一个在环内 一个在环外
    //第二种情况 两个都在环内
    void Get_Link_CrossCircleNode(pNode pHead1, pNode pHead2)
    {
    	pNode meet1 = GetCircleEnterNode(pHead1, CheckCircle(pHead1));
    	pNode meet2 = GetCircleEnterNode(pHead2, CheckCircle(pHead2));
    
    	if (meet1 == meet2)//一个在环内一个在环外
    	{
    		pNode pCur = _Get_Link_CrossNode(pHead1, pHead2);//此函数在12题中有写
    		printf("交点一： %d  交点二： %d\n", meet1->_data, pCur->_data);
    	}
    	else//两个点都在环内
    	{
    		pNode p1 = CheckCircle(pHead1);
    		pNode p2 = CheckCircle(pHead2);
    		printf("交点一： %d  交点二： %d\n", p1->_data, p2->_data);
    	}
    }

[SouthEast]: /images/20220613/45356f4bf51542f38c437b139cd23290.png
[SouthEast 1]: /images/20220613/188fe2a0f2af4d41a2ac6f624b5fd874.png
[SouthEast 2]: /images/20220613/bc2f94173beb49429612d1a7fa6ad440.png
[SouthEast 3]: /images/20220613/684c4a3c003948d39acc83e159aecc84.png
[SouthEast 4]: /images/20220613/48e539df00dc4f58be3f2bbae6ba2dea.png
[SouthEast 5]: /images/20220613/8396e4eec85541d5b1fec0bc3e4f2d43.png