142. 环形链表 II

力扣题目链接 (opens new window)

题目描述

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

为了表示给定链表中的环，评测系统内部使用整数 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, 10^4] 内
• -10^5 <= Node.val <= 10^5
• pos 的值为 -1 或链表中的一个有效索引

思路

本题要解决两个问题：

1. 如何判断链表中是否有环？
2. 如果有环，如何找到环的入口？

判断链表是否有环

判断有没有环，使用快慢指针：

• slow 每次走一个节点；
• fast 每次走两个节点；
• 如果链表无环，fast 会先到达链表末尾；
• 如果链表有环，fast 和 slow 一定会在环内相遇。

为什么两个指针一定会相遇，而不是一直错开呢？

两个指针都进入环后，fast 每轮比 slow 多走一个节点。相对于 slow，fast 每次只靠近一个节点，所以不会跳过 slow，最终一定会与它重合。

这部分与141. 环形链表完全一致。真正需要想清楚的是：相遇以后，怎样定位环的入口？

找到环的入口

假设：

• 从头节点到环入口的距离为 x；
• 从环入口到相遇节点的距离为 y；
• 从相遇节点回到环入口的距离为 z。

快慢指针相遇时，slow 走过的距离为：

x + y

fast 在环内比 slow 多走了 n 圈，因此它走过的距离为：

x + y + n(y + z)

又因为 fast 每次走两步，slow 每次走一步，所以：

2(x + y) = x + y + n(y + z)

整理可得：

x = (n - 1)(y + z) + z

这个公式就是定位入口的关键。

从相遇节点出发，先走 z 个节点会到达环入口；多走的 (n - 1)(y + z) 只是又绕了若干整圈，最终仍然停在环入口。

因此可以让两个指针分别从头节点和相遇节点出发，每次都走一个节点。头节点一侧走过 x 个节点时到达环入口；相遇节点一侧也恰好到达环入口。

两个指针再次相遇的节点，就是环的入口。

模拟过程

以 head = [3,2,0,-4]，pos = 1 为例，尾节点 -4 指向节点 2。

第一阶段，用快慢指针寻找环内相遇点：

1. 初始时，slow 和 fast 都指向头节点 3。
2. 第一轮后，slow 指向 2，fast 指向 0。
3. 第二轮后，slow 指向 0，fast 指向 2。
4. 第三轮后，两个指针都指向 -4，确认链表有环。

第二阶段，从头节点和相遇节点同时出发：

1. index1 指向相遇节点 -4，index2 指向头节点 3。
2. 两个指针各走一步后，都指向节点 2。
3. 两个指针相遇，节点 2 就是环的入口。

整个寻找入口的过程如下：

解题代码

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;

            if (slow == fast) { // 第一次相遇，说明链表中存在环
                ListNode* index1 = slow;
                ListNode* index2 = head;

                // 从相遇点和头节点同时出发，再次相遇处就是环入口
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }

        return nullptr;
    }
};

复杂度分析

• 时间复杂度：O(n)。寻找相遇点和寻找环入口都只需要线性时间。
• 空间复杂度：O(1)。只使用了常数个指针。

其他语言

Python3

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow is fast:  # 第一次相遇，说明链表中存在环
                index1 = slow
                index2 = head

                while index1 is not index2:
                    index1 = index1.next
                    index2 = index2.next
                return index1

        return None

Java

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) { // 第一次相遇，说明链表中存在环
                ListNode index1 = slow;
                ListNode index2 = head;

                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }

        return null;
    }
}

Go

func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head

    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next

        if slow == fast { // 第一次相遇，说明链表中存在环
            index1, index2 := slow, head

            for index1 != index2 {
                index1 = index1.Next
                index2 = index2.Next
            }
            return index1
        }
    }

    return nil
}

JS

var detectCycle = function(head) {
    let slow = head;
    let fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) { // 第一次相遇，说明链表中存在环
            let index1 = slow;
            let index2 = head;

            while (index1 !== index2) {
                index1 = index1.next;
                index2 = index2.next;
            }
            return index1;
        }
    }

    return null;
};

与代码随想录联系

本题是141. 环形链表的进阶：141 题只需要判断链表中是否有环，本题还要通过数学关系找到环的入口。

代码随想录的链表章节已经对这个推导进行了完整讲解，可以结合142. 环形链表 II继续理解快慢指针为什么能够定位入口。