寻找链表环入口的算法证明

寻找链表环入口是一道经典算法题目Linked List Cycle II,其解法是比较技巧性的快慢指针,写起来比较简单。真正的难点在于如何去证明解法的正确性。网上许多证明难以理解(没,我没证据),并且思路没有普适性,本文将会提供一种比较简洁且可移植的证明思路。

先回顾下题目:

给定一个单向链表(singly-linked-list)的头结点head,返回该链表的环入口。如下图所示,函数应该返回指向节点值为2的指针。
Circular Linked List

本题的最优解法是使用快慢两个指针,都从head开始出发,慢指针每次走一步,快指针每次走两步。当他们相撞的时候把快指针重新指向head,慢指针保留在相撞位置。并且从此时开始快慢指针的前进速度都改成一步,直到它们再次相撞的位置就是环的入口。详细代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(!head)
return nullptr;

//寻找碰撞点
ListNode *slow = head, *fast = head;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
break;
}

if(fast==nullptr || fast->next==nullptr)
return nullptr;

//寻找环入口
fast = head;
while(slow != fast){
slow = slow->next;
fast = fast->next;
}
return slow;
}
};

证明

接下来我们将会对这种解法进行证明,如下图所示将一个环形链表分为三个部分,分别为a,b和c代表此部分链表的长度(length),其中a的末端是环入口。
Circular Linked List

  1. 定义slow, fast分别为链表的快慢指针,slow每次前进一步,fast每次前进两步。
  2. 可以证明当快慢指针相撞的时候,它们相撞的时间点必定是慢指针进入环后的第一圈。(提示:根据快慢指针的定义并使用矛盾证法:proof-by-contradiction)。假设它们在图示的碰撞点处碰撞,那么此时slow,fast两个指针走过的步数分别为:

slow : a+b
fast : 2(a+b)
  1. 假设有环形链表指针p1, p2,我们定义符号:=的意义为:若p1 := p2则p1和p2指向环形链表的同一个节点。
    根据环形链表指针加减法的定义,有如下的法则:

若p1 := p2,且k为一个整数,则:
p1+k := p2+k
  1. 因为快慢指针在碰撞点相撞,且他们都是从head开始出发,所以可以得到下面的等式:

head+(a+b) := head+2(a+b)

根据上图的环形链表,有下列等式:


head+(a) := head+(a+b+c)

值得提醒的是a,b,c为整数长度(length),而head为指针,上面的等式进行的是指针的加减法(pointer arithmetic)。
为了方便表示,我们省略head,并默认等式两边都加上了head,那么可以得到下面的简化表示:


a+b := 2(a+b)
a := a+b+c

我们在前面有提到过上述算法在找到碰撞点后把fast重新指向head然后再向前一次走一步,直到快慢指针碰撞,那么如果它们碰撞时的位置的确为环入口的话那么必定有这个等式成立:a+b+a := a。你会问为什么?解析是:假设上述算法是正确的,那么第一次碰撞时slow走的步数为a+b,此时fast重新指向了头结点。根据算法中的描述,当再次碰撞的时候fast和slow在原来的基础上又走了a步(别忘了此时它们的速度已经变成一样了),此时slow = head+a+b+a指向了环入口,fast = head+a也指向了环入口,所以我们有简化式子a+b+a := a。只要证明这个式子正确,就可以确定slow指针从head出发经过了a+b+a步最终到达环入口。返回该处的指针即是题目要求的答案。

  1. 现在集中精力来证明这个等式是成立的:

核心部分


//别忘了这只是为了方便我们观察的简化表示,
//完整表达式中:=的左右应该都是指针

我们有:
a+b := 2(a+b) (1)
a := a+b+c (2)

那么
a+b+a := a+b+(a+b+c) //利用(2)
:= 2(a+b)+c
:= a+b+c //利用(1)
:= a //利用(2)

证明完毕

到此我们对于上述算法的确能够找到环入口的证明完毕,其实上面一大段都只是为了保持文章的完整性做的详细说明,真正的证明其实非常简短,就是核心部分,只要你对符号:=的定义了解,那么很容易就能够通过纯数学变换重新写出这份证明。我们的思路具有普适性,同样使用定义的符号:=可以证明寻找相交链表交点的算法正确性Intersection of Two Linked Lists,有机会(通常隐含的意思是我懒得写)我会对此进行扩展说明。