题目

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

本题介绍Floyd龟兔判环算法（基于快慢指针），还有其他判环算法，详见：https://en.wikipedia.org/wiki/Cycle_detection

解析

如果链表上存在环，那么在环上以不同速度前进的两个指针必定会在某个时刻相遇。算法分为两个阶段

阶段1

龟一次走一步，兔子一次走两步
当兔子能走到终点时，不存在环
当兔子能追上龟时，可以判断存在环

阶段2

从它们第一次相遇开始，龟回到起点，兔子保持原位不变
龟和兔子一次都走一步
当再次相遇时，地点就是环的入口

为什么呢？

设起点到入口走 a 步（本例是 7），绕环一圈长度为 b（本例是 5），
那么从起点开始，走 a + 绕环 n 圈，都能找到环入口
第一次相遇时
- 兔走了 a + 绕环 n 圈（本例 2 圈） + k，k 是它们相遇距环入口位置（本例 3，不重要）
- 龟走了 a + 绕环 n 圈（本例 0 圈） + k，当然它绕的圈数比兔少
- 兔走的距离是龟的两倍，所以龟走的 = 兔走的 - 龟走的 = 绕环 n 圈
而前面分析过，如果走 a + 绕环 n 圈，都能找到环入口，因此从相遇点开始，再走 a 步，就是环入口
此时可以看成已经走了n圈，所以在相遇点再走a步就可以到达环入口，但是a的距离是多少并不知道。可以利用1个小技巧：龟回到起点开始走（走a步也会到起点相当于n = 0）每次走一步，兔在原地每次走一步，（走a步后也会到达环入口，相当于a+n | n=（任意值）），即龟兔再次相遇时他们都已经走了a步，相遇点（满足 a + n）即为环入口。

Java代码实现：

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public static ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                slow = head;
                while (true) {
                    if (slow == fast) {
                        return slow;
                    }
                    slow = slow.next;
                    fast = fast.next;
                }
            }
        }

        return null;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(4);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2;
        ListNode node = detectCycle(node1);
        System.out.println(node==null ? null : node.val);

    }
}

输入：

输入：2

end

如何找到一个环形链表的环入口

题目

解析

评论