day135—快慢指针—环形链表Ⅱ（LeetCode-142）

题目描述

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

如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果pos是-1，则在该链表中没有环。注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1输出：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0输出：返回索引为 0 的链表节点解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1输出：返回 null解释：链表中没有环。

提示：

• 链表中节点的数目范围在范围[0, 104]内
• -105 <= Node.val <= 105
• pos的值为-1或者链表中的一个有效索引

解决方案：

这段代码的核心功能是在单链表中找到环形结构的入口节点（若链表无环则返回nullptr），是判断链表环的进阶问题，依然采用「快慢指针」解法，结合数学推导定位环入口，时间复杂度O(n)、空间复杂度O(1)，是该问题的最优解法。

核心逻辑

代码分两步完成：先通过快慢指针判断是否有环并找到相遇点，再利用数学规律定位环入口：

1. 第一步：找快慢指针相遇点
   • 慢指针slow、快指针fast均从表头出发，慢指针每次走 1 步，快指针每次走 2 步；
   • 若链表有环，快慢指针必会在环内相遇；若快指针走到末尾（fast或fast->next为空），说明无环，直接返回nullptr。
2. 第二步：定位环入口
   • 相遇后，将快指针fast重置到链表头节点，且快指针改为和慢指针同速（每次走 1 步）；
   • 快慢指针继续同步移动，当二者再次相遇时，相遇节点就是环的入口节点，返回该节点即可。

总结

1. 核心思路：利用「快慢指针相遇」证明有环，再通过「同速指针从头和相遇点出发必在环入口相遇」的数学规律定位入口；
2. 关键规律：设表头到环入口距离为a，环入口到相遇点距离为b，环长为c，则相遇时快指针走的距离a + n(b+c) + b是慢指针a + b的 2 倍，推导得a = (n-1)c + (c - b)，即表头到入口的距离等于相遇点绕环到入口的距离；
3. 效率优势：全程仅用两个指针，无额外空间开销，时间复杂度O(n)，是找环入口的最优解法。

函数源码：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode* slow=head; ListNode* fast=head; while(fast && fast->next){ slow=slow->next; fast=fast->next->next; if(fast==slow){ fast=head;//重置位置和速度 while(slow!=fast){ fast=fast->next; slow=slow->next; } return slow; } } return nullptr; } };