【链表OJ 10】环形链表Ⅱ(求入环节点)

news/2024/5/16 22:08:43/文章来源:https://blog.csdn.net/weixin_65186652/article/details/132638522

前言:

💥🎈个人主页:Dream_Chaser～ 🎈💥

✨✨刷题专栏:http://t.csdn.cn/UlvTc

⛳⛳本篇内容:力扣上链表OJ题目

leetcode142. 环形链表 II

1.问题描述

2.代码思路

3.问题分析

leetcode142. 环形链表 II

来源: 142. 环形链表 II - 力扣（LeetCode）

1.问题描述

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null

题解接口：

struct ListNode *detectCycle(struct ListNode *head) {}

2.代码思路

前提条件：

是fast走的路程是slow的2倍。

解题思路:

第一步,先定义一个快指针fast以及一个慢指针slow,这里跟环形链表1的快慢指针的操作一致，不作详细说明。之后找到可以证明链表带环的相遇点，并定义meet指针指向slow或此时的fast。

第二步:接着让head指针从链表第一个节点开始移动，meet指针从相遇点开始移动，然后它们将会在链表带环的入口处相遇。(这是这道题思考的方向，但是如何去证明呢？)

代码实现:
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* fast=head,*slow=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;//带环(如果条件成立，则证明该链表为带环链表)if(slow == fast) {struct ListNode*meet=slow;  //求入环点 while(head!=meet){head=head->next;meet=meet->next;}return meet;//返回链表开始入环的第一个节点}}return NULL;//如果链表无环，则返回 null
}
代码执行:

3.问题分析

结论证明:

一个指针从相遇点(meet)走，一个指针从链表头(head)开始走，他们会在入口点(返回值)相遇。为什么?以下是证明:

假设:

链表头--环入口点距离:L

环入口点--相遇点距离:X

环的长度:C

依据题意求出slow指针所走过的距离，明显是L+X

然后思考一个问题:有没有可能slow进环转了几圈才追上?

答:不可能! 1圈之内，fast必然追上slow，因为他们之间距离每次缩小1，不会错过，slow走1圈，fast都走了2圈了，肯定追上了。

所以说可以简单的求出fast指针在环上走过的距离:L+C ＋X ，并且根据

        2*(L+X) = L+C+X

        L+X = C

第一种情况:L=C-X -->可以求出链表头到环入口点距离

        试想一下,当L的距离越长，环的大小越小，那么L=C-X依旧成立吗？

由图可得, 可得到第二个结论:L=(n-1)*C+C-X (n-1)*C表示fast在环内转了（n-1）圈

总结:无论是第一种情况，还是第二种情况，meet与head均会在入环处相遇。