142.环形链表 II (Medium)*

题目描述*

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

说明*

不允许修改给定的链表。

进阶*

是否可以不用额外空间解决此题？

代码*

还是用双指针方法，下面通过数学方式推导入环点的位置。

设 head 到入环点的距离为 $x$ ，入环点到相遇点的距离为 $y$ ，环的长度为 $n$ 。

slow 指针走过的距离为 $x + y + s \times n$ ，fast 指针走过的距离为 $x + y + t \times n$ 。fast 速度是 slow 的二倍，则有：

$\begin{aligned} x + y + t \times n & = 2(x + y + s \times n) \\ t \times n & = x + y + 2 \times s \times n \\ x & = (t - 2\times s -1) \times n + n - y \\ x & = n - y\ (mod\ n) \end{aligned}$

因此，我们只要让双指针从链表头和相遇点同时遍历，相遇即同时到达入环点。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head, *slow = head;
        ListNode *meet = head;
        while(fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) {
                while(meet != slow) {
                    meet = meet->next;
                    slow = slow->next;
                }
                return meet;
            }
        }
        return nullptr;
    }
};

最后更新: July 23, 2022