142. Linked List Cycle II

Leetcode Linked List Two Pointers

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up: Can you solve it without using extra space?

分析

这道题目是LeetCode 141. Linked List Cycle的升级版，前者只需要给出链表是否存在环，现在还要给出环的起始位置。由于Q141有两种解法：一种是哈希表，另一种是两个指针。这里也分别用这两种方法解决问题。

利用HashSet:

public ListNode detectCycle(ListNode head) {
    HashSet<ListNode> map = new HashSet<>();
    while (head != null) {
        if (map.contains(head)) return head;
        map.add(head);
        head = head.next;
    }
    return null;
}

利用指针来寻找链表中环的位置，一共分为两个步骤：

1. 确定是否有环
   • 使用慢指针每次移动一步
   • 使用快指针每次移动两步
   • 如果慢指针和快指针在一定时间后相遇，则有环；如果快指针到达链表尾部，则无环。
2. 如果存在环，返回环的起点pt
   • $s$是起点start和环的起点ep(entry point)的距离
   • $m$是环的起点ep和相遇点meet的距离
   • $r$是环的长度
   • $n$是慢指针和快指针首次相遇它们绕着环运动的圈数
   • 因为快指针的速度是慢指针的两倍，所以 $s+m = \frac{s+m+n\times r}{2}\rightarrow s+m = n\times r \rightarrow s = (n-1)\times r + (r - m)$，
   • 所以有结论：起点start和环的起点ep(entry point)的距离$s$等于相遇点meet和环的起点ep沿着环的方向的距离。
   • 所以，当慢指针和快指针相遇的时候，我们放另一个慢指针在起点start，然后把快指针变成慢指针。同时移动两个慢指针，它们相遇时的位置，刚好是环的起点ep($s = (n-1)\times r + (r - m)$)。

public ListNode detectCycle(ListNode head) {
    // 快指针和慢指针
    ListNode fast = head, slow = head;

    // 确定环是否存在于链表当中
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (slow == fast) break; // 存在环：相遇
    }

    // 不存在环
    if (fast == null || fast.next == null) return null;

    // 在链表首部放置慢指针
    slow = head;

    // 同时移动两个慢指针(快指针也变成慢指针),直到相遇
    while (fast != slow) {
        fast = fast.next;
        slow = slow.next;
    }

    return fast;
}