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

如何找带环的单链表里的环入口点?这是一个非常有意思的问题,解完之后,会让你感觉算法很美,很享受。其实已经有很多人谈这个问题的解法了,这里我主要想结合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;
}

王辉 wechat
交流或订阅,请长按或扫描上方微信二维码