给定一个链表,返回链表入环的第一个节点。如果不存在环,则返回 null

为了表示链表中的环,我们使用一个整数 pos 来表示尾部节点指向节点的索引。如果 pos-1,表示链表中不存在环。

提示: 不要修改链表。

例一:
输入: head = [3,2,0,-4], pos = 1
输出: 尾部节点连接的索引为 1 的节点
解释: 链表中存在环,尾部节点连接到了第二个节点。

例二:
输入: head = [1,2], pos = 0
输出: 尾部节点连接的索引为 0 的节点
解释: 链表中存在环,尾部节点连接到了第一个节点。

例三:
输入: head = [1], pos = -1
输出: 不存在环
解释: 链表中不存在环。

/*
 * 142. Linked List Cycle II
 * https://leetcode.com/problems/linked-list-cycle-ii/
 * https://realneo.me/142-linked-list-cycle-ii/
 */

public class DetectCycle {
    public static void main(String[] args) throws InterruptedException {
        ListNode head = new ListNode(1);
        ListNode node = head;
        for (int i = 2; i < 10; i++) {
            node.next = new ListNode(i);
            node = node.next;
        }

        DetectCycle solution = new DetectCycle();

        System.out.println(solution.detectCycle(head));

        node.next = head.next.next.next;

        System.out.println(solution.detectCycle(head).val);
    }

    private ListNode detectCycle(ListNode head) {
        //快慢法查找
        ListNode slow = head;
        ListNode fast = head;

        do {
            if (fast == null || fast.next == null)
                return null;
            slow = slow.next;
            fast = fast.next.next;
        } while (slow != fast);

        //此时从头部开始走,走到同一位置时刚好是进入循环
        while (head != slow) {
            slow = slow.next;
            head = head.next;
        }

        return head;
    }
}