动画解释如何求单链表环入口点

发表于

如何找带环的单链表里的环入口点？这是一个非常有意思的问题，解完之后，会让你感觉算法很美，很享受。其实已经有很多人谈这个问题的解法了，这里我主要想结合Canvas动画，让你更生动形象的感受这个问题的美妙。

具体问题是，给你一个含有环的单链表，求环的入口点。比如我们有一个链表，从0一直链到16，然后16转过身来又链到了5。这个链表里，5到16组成了一个环，环的入口点是5。

我在解这个问题之前，知道如何判断单链表是否有环，利用的是龟兔赛跑法。所谓龟兔赛跑，指的是用两个指针，兔子(蓝色)每次移动两个节点，乌龟(红色)每次一个，如果有环的话，兔子和乌龟有朝一日都会进入这个环。由于兔子比乌龟跑的快，他们在环里，肯定会相遇。

知道了如何判断是否有环，离找到环入口点就不远了。其实环的入口点，和他们在环里的相遇点是有关系的。现在停下来想一下，他们会在哪里相遇？如果想不通的话，就多跑几下上面的Canvas动画。

下面是用Java解的这道题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
LinkedListNode detect(LinkedListNode head) {
    LinkedListNode runner = head;
    LinkedListNode walker = head;
    while (runner != null && runner.next != null) {
        runner = runner.next.next;
        walker = walker.next;
        if (runner == walker) break;
    }
    if (runner == null || runner.next == null) return null;

    walker = head;
    while (runner != walker) {
        runner = runner.next;
        walker = walker.next;
    }
    return runner;
}