LeetCode Note Java 00142：Linked List Cycle II

回傳輸入的 Linked List 的 Cycle 啟始 ListNode。

題目

Linked List Cycle II Medium

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

解法

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        // Cycle 測試：fast 終會追上 slow
        while (slow.next != null && fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // 確定是 Cycle
                // head 到 Cycle start node 的距離與 slow 到 Cycle start node 距離會一致：
                // 因為 a + b = (a + 2b +c ) / 2
                // 2a + 2b = a + 2b + c
                // a = c
                while (head != slow) {
                    head = head.next;
                    slow = slow.next;
                }
                return head;
            }
        }
        return null;
    }
}

這題我真的想不到，所以直接看別人答案了，感覺我就算好好在紙上畫圖分析，並測試幾輪後也想不到這種解法。

參考資料

[Day 16] 演算法刷題 LeetCode 142. Linked List Cycle II (Medium)