链表之第三回

news/2024/5/9 10:49:24/文章来源:https://blog.csdn.net/m0_66780695/article/details/132380184

在这里插入图片描述

欢迎来到我的：世界

该文章收入栏目：链表

希望作者的文章对你有所帮助，有不足的地方还请指正，大家一起学习交流 !

前言

今天的天气很不错😸，大早上起床，晨跑3公里，好久没这么跑了，真的很不错，我喜欢汗淋淋的感觉😄；暑假的假期时间也快到了，珍惜珍惜拥有自己所能支配的时间，来写几题吧✍️；

第一题：判断是否为环形链表

地址：oj地址

在这里插入图片描述
解题思路：

思路： 设置快慢指针，快指针 fast 每次走两个结点，慢指针 slow 每次走一个结点；如果是环形的，fast指针一定会和slow指针相遇，而且fast ，fast->next 走不到空(根据这两点做判断条件)；如果不是环形，fast和slow一定不会相遇；可以根据这样的思路来写代码：
注意：
这个思路要想清楚

第一步

第二步：

第三步：相遇

代码实现：

bool hasCycle(struct ListNode *head) {struct ListNode *slow,*fast;//设置快慢指针slow=fast=head;//开始走，判断while(fast && fast->next){fast=fast->next->next; //快指针一次走两步slow=slow->next;	   //慢指针一次走一步	if(fast==slow)//相遇则代表是环形{return true;}}//对于环形单链表，不可能有指向空指针return false;
}

第二题：找到两条链表的相交点

地址：oj地址

在这里插入图片描述

解题思路：

思路： 首先要判断，既然他如果是相交的，那最起码是有最后一个节点是相交的吧，那就判断两条链表最后一个结点是不是一样的；要知道应该是从相交点开始后面的所有结点应该都相等，所以重点就在相交结点前；

创造两个变量count1，count2，计算两条链表的结点总数;创造两个指针cur1，cur2指向两条链表的头结点headA，headB，由cur1和cur2去找最后一个结点(这里注意:判断的条件应该是cur1所指向的next !=NULL,因为这里我们要找到最后一个结点)，计算两条链表的各结点的数量count1，count2，先让长的链表头结点先走 | count1 - count2 | (绝对值可以用 abs这个函数 )步，这个时候就可以两条链表的从头结点开始比较，如果相等则返回这个结点，如果不相等，就走向下一个结点直到找到相交结点(这里一定会找到相交结点，因为在上面的时候已经将不相交的情况排除了)；

第一步：计算出两条链表的结点数量

第二步： 让长的链表头结点先开始走 | count1 - count2 | 步，注意这里用到绝对值；

第三步：开始进行比较判断，如果相等则返回这个结点，如果不相等，就走向下一个结点直到找到相交结点；

注意：这里让长的链表先走，一般想法是用if语句；这里我想换个更方便的方法：创造两个指针变量fast，slow；分别指向两条链表的头结点，这里只要一个判断：如果count1 小于 count2 让fast指向headB，而slow指向headA；思想就是始终让fast指向的是长链表，slow指向短一点的链表；在之后就可以直接使用fast，slow变量了；

代码实现：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {int count1=1,count2=1;//计算两条链表的结点总数struct ListNode *cur1=headA;struct ListNode *cur2=headB;//找到headA链表的最后一个结点while(cur1->next){cur1=cur1->next;++count1;}//找到headB链表的最后一个结点while(cur2->next){cur2=cur2->next;++count2;}//结点不相等，则不可能相交；if(cur1!=cur2){return NULL;}  //绝对值int len =abs(count1-count2);//始终让fast指向长链表，slow指向短一点的链表；struct ListNode*fast=headA,*slow=headB;if(count1<count2){fast=headB;slow=headA;}//让其从相同位置结点开始比较；while(len--){fast=fast->next;}//比较while(fast != slow){fast=fast->next;slow=slow->next;}return fast;}

第三题：返回环形链表入环的那个结点

地址：oj地址

在这里插入图片描述
解题思路：

第一个简单的思路：

设置两个指针fast和slow，fast一次走两步slow一次走一步，在环里的肯定会相遇，我们需要找到相遇的那个结点，然后断开这个结点与他后一个节点的链接，这样求入环点的问题就变成了：求两条链表的相交点；而求相交点的问题已经在上面解决了，是不是很简单理解；

将相遇点变成相交链表的尾巴，置成空；然后将相遇点tem下一结点设置成newnode指针，然后就是找相交点的问题了；

代码实现：

//实现找到相交结点并返回
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {int count1=1,count2=1;//计算两条链表的结点总数struct ListNode *cur1=headA;struct ListNode *cur2=headB;//找到headA链表的最后一个结点while(cur1->next){cur1=cur1->next;++count1;}//找到headB链表的最后一个结点while(cur2->next){cur2=cur2->next;++count2;}//结点不相等，则不可能相交；if(cur1!=cur2){return NULL;}  //绝对值int len =abs(count1-count2);//始终让fast指向长链表，slow指向短一点的链表；struct ListNode*fast=headA,*slow=headB;if(count1<count2){fast=headB;slow=headA;}//让其从相同位置结点开始比较；while(len--){fast=fast->next;}//比较while(fast != slow){fast=fast->next;slow=slow->next;}return fast;
}struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *fast=head,*slow=head;struct ListNode *tem=NULL,*newnode=NULL;while(fast && fast->next){fast=fast->next->next;slow=slow->next;//找到相遇点if(slow==fast){tem=slow;newnode=tem->next;//将相遇点变成链表的尾巴，置空；tem->next=NULL;//这边用我们之前写的求出相交结点return getIntersectionNode(head,newnode);}}return NULL;
}

这是一个思路比较容易理解的版本；还有一个比较难理解的思路：
是相似于物理的追击问题；
为来利用图解的方式；先进行这些假设：

这时候根据物理上的追击问题，根据fast和slow到相遇点所走的路程是一个两倍的关系；

所以：fast所走的距离是slow所走的距离的两倍；
slow走的距离是：L+X
fast走的距离是：L+X+n*C

这里详解一下为什么fast走的距离是：L+X+n*C
首先fast比slow走到快，当slow刚进入环，可能fast已经走了n圈环了(这个也是根据链表头结点到入环点的距离来判断的)，且至少走了一圈了，当然不管他fast会绕多少圈，但他始终会在距离入环点 X的距离上的相遇点相遇的；

知道fast和slow所走的路程就可以用一个方程式：
2 * (L+X) = L+X+n * C （n>=1）化简得：
L = n * C - X
知道C - X 就是入口点；

无论fast走了多少圈C，C-X的距离就是相遇点到入环点的距离，无非是多绕了几圈，但是他们一定会在入环点相遇；

得出结论：一个指针从起点走，一个指针从相遇点走，他们一定会在入口点相遇；

代码的实现：

struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *fast=head,*slow=head;//快慢指针struct ListNode *tem=NULL;//相交点//成环进while(fast && fast->next){fast=fast->next->next;slow=slow->next;//找到相遇点if(slow==fast){tem=slow;//开始找交点while(head!=tem){head=head->next;tem=tem->next;}return tem;}}//不成环就返回空return NULL;
}