https://leetcode.cn/problems/linked-list-cycle-ii/

题面

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

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

说明：不允许修改给定的链表。

循环链表

思路：快慢指针，时间O(n)，空间O(1)

主要考察两个知识点：

  • 判断链表是否有环
  • 如果有环，如何找到这个环

判断链表是否有环

可以用快慢指针，fast每次走两步，slow每次走一步，如果有环，它们一定会相遇。

如果有环，如何找到这个环

已经判断链表有环了，那么接下来要找这个环的入口。

可以用一点数学知识，可以得出等式：
2(x+y) = x+y+n(y+z) (n是指慢指针进入环之前，快指针已经在环内跑的圈数)
=> x+y = n(y+z)
=> x=n(y+z)-y
=> x=(n-1)(y+z)+z
从上式能看得出y+z是一圈的长度，n-1是代表快指针在圈内多转了多少圈，这个不重要，因为x和z的关系已经可以看得出来了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 = fast;
            ListNode index2 = head;
            // 两个指针，从 头节点 和 相遇节点，各走一步，直到相遇，此时相遇点就是环入口
            while (index1 != index2) {
                index1 = index1.next;
                index2 = index2.next;
            }
            return index1;
        }
    }
    return null;
}