142. Linked List Cycle II

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                // 设走了 n 次，则 fast 走了 2n 步，slow 走了 n 步
                // 设环外 a 个节点，环内 b 个节点，则 fast 比 slow 多走了 x 圈，即多走了 xb 步
                // fast = 2n, slow = n, 根据多走了 xb 步可知 2n - n = xb, 易知 n = xb 即 slow 走了 xb 步，且我们知道从起点走到环入口节点需要走 a + xb 步
                // 那么再让 slow 走 a 个节点即可到达环的入口节点

                ListNode curr = head;
                while (curr != slow) {
                    curr = curr.next;
                    slow = slow.next;
                }
                return curr;
            }
        }

        return null;
    }
}

Reference

142. Linked List Cycle II
剑指 Offer II 022. 链表中环的入口节点