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) {
                // 存在环
                // 设环外 a 个节点，环内 b 个节点，在环内绕了 n 圈后相遇，共移动了 x 次
                //                        * * * * * *
                //                                *   *
                //                                  *
                // 可知 slow 节点移动节点数为 x, fast 节点移动节点数为 2x, 推导出 2x - x = bn
                // 即 x = bn, 即 slow 节点位于 bn 处，而 a + bn 是相遇的节点，那么使 slow 节点再移动 a 个节点即可到达相遇节点
                ListNode node = head;
                while (node != slow) {
                    node = node.next;
                    slow = slow.next;
                }
                return node;
            }
        }

        return null;
    }
}

References

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