链表中环的入口节点

如何链表中包含环，如何找出环的入口节点? 例如，在如图所示的链表中，环的入口节点是节点 $3$。

解决这道题的思路分为两步，第一步是确定该链表有没有环，我们定义两个指针，一个快指针，一个慢指针，快指针一次性走两步，慢指针一次性走一步。如果有环的话，那么快指针和慢指针就会相遇，并且是在环内相遇；如果没有环的话，那么快指针就会到达尾节点，慢指针与快指针不会相遇。

public static ListNode meetingNode(ListNode root) {
    if (root == null) {
        return null;
    }
    // 慢指针先走一步
    ListNode slow = root.next;
    if (slow == null) {
        return null;
    } 
    // 快指针先走两步
    ListNode fast = slow.next;
    while (slow != null && fast != null) {
        if (slow == fast) {
            return fast;
        }
        slow = slow.next;
        fast = fast.next;
        if (fast != null) {
            fast = fast.next;
        }
    }
    return null;

第二步就是确定环的入口节点，首先我们拿到在第一步中快慢指针相遇的节点，让这个节点遍历环以统计环的数目，当这个节点回到原地时即走了一圈。拿到环的数目 $k$ 以后，我们继续定义两个指针，一个指针先走 $k$ 步，然后两个指针继续走，当两个指针相遇时，即是环的入口节点

public static ListNode entryNodeOfLoop(ListNode root) {
    // 获得相遇的节点
    ListNode meetingNode = meetingNode(root);
    if (meetingNode == null) {
        return null;
    }
    // 统计环中节点数目
    int count = 1;
    ListNode loopNode = meetingNode;
    while (loopNode.next != meetingNode) {
        count++;
        loopNode = loopNode.next;
    }
    ListNode ahead = root;
    ListNode after = root;
    // ahead 先走 count 步
    for (int i = 0; i < count; i++) {
        ahead = ahead.next;
    }
    // 相遇节点即为环的入口节点
    while (ahead != after) {
        ahead = ahead.next;
        after = after.next;
    }
    return after;
}

测试如下

public static void main(String[] args) {
    ListNode root = new ListNode(1);
    root.next = new ListNode(2);
    root.next.next = new ListNode(3);
    root.next.next.next = new ListNode(4);
    root.next.next.next.next = new ListNode(5);
    root.next.next.next.next.next = new ListNode(6);
    root.next.next.next.next.next.next = root.next.next;
    ListNode entryNode = entryNodeOfLoop(root);
    System.out.println(entryNode != null ? entryNode.value : "null"); // 3
}