链表的相交和带环问题详解

本文主要是介绍链表的相交和带环问题详解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

弃我去者，昨日之日不可留；乱我心者，今日之日多烦忧。长风万里送秋雁，对此可以酣高楼。蓬莱文章建安骨，中间小谢又清发。
俱怀逸兴壮思飞，欲上青天揽明月。抽刀断水水更流，举杯消愁愁更愁。人生在世不称意，明朝散发弄扁舟。
——李白

文章目录

- 判断链表是否相交
- 求两个相交链表的交点
- 判断链表是否带环
- 求带环链表的环入口点

请添加图片描述

判断链表是否相交

思路:如果两个链表的最后一个节点是同一个节点,那一定相交
注意:这里不是值相等就是同一个节点.
这个代码我就不敲了,比较简单,而且求交点的代码里面有

求两个相交链表的交点

//给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {//判断链表是否为空if(headA==NULL||headB==NULL){return NULL;}//判断是否相交struct ListNode* cura=headA;struct ListNode* curb=headB;
//注意,int sizea,sizeb=1;  这种写法会默认sizea是0,导致错误int sizea=1;int sizeb=1;while(cura->next){cura=cura->next;sizea++;}while(curb->next){curb=curb->next;sizeb++;}if(cura!=curb){return NULL;}//相交 长链表先走差值步struct ListNode* curA=headA;struct ListNode* curB=headB;int gap=sizea-sizeb;if(gap>0){while(gap){curA=curA->next;gap--;}}else{while(gap){curB=curB->next;gap++;}}//对齐之后一起走,直到遇到同一个节点
while(curA!=curB){curA=curA->next;curB=curB->next;}return curA;}

判断链表是否带环

方法:快慢指针
主要分析:
快指针为什么一次走两步慢指针一次走一步,如果是快指针一次走三步走四步可不可以?
不可以
因为快指针一次走两步与慢指针的步数差是1,而一个环最小的节点数是2,就不会发生每次快指针都恰好绕过一圈而导致的快慢指针不相遇的问题

在这里插入图片描述
画一个简单的图来看,如果快指针一次走三步,就会恰好每次都错过慢指针

下面是代码实现

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {//用快慢指针,快指针一次两步,慢指针一次一步,带环一定相遇struct ListNode* fast=head;struct ListNode* low=head;while(fast&&fast->next){fast=fast->next->next;low=low->next;if(fast==low){return true;}}return false;}

求带环链表的环入口点

在这里插入图片描述
方式一:
从相遇点的位置将环断开,就转化成求两个链表交点问题,最后不要忘记将环合上.
方式二:
(这是大佬的方法,让我们一起学习一下)

下图是这个方法的证明过程,比较复杂需要画图理解,有点像数学几何的思想,仔细看这个过程,不复杂只是很巧妙!
在这里插入图片描述
下面是方式二的代码实现

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode node;
node* hascycle(node*head)
{node* fast=head;node* low=head;while(fast&&fast->next){fast=fast->next->next;low=low->next;if(fast==low){return fast;}}return NULL;
}
struct ListNode *detectCycle(struct ListNode *head) {if(head==NULL){  return NULL;}node* pm=hascycle(head);node* ph=head;if(pm==NULL){return NULL;}while(pm!=ph){pm=pm->next;ph=ph->next;}return pm;
}