数据结构考试题

上课没听导致做不出来。。

快慢指针

设指针 slow,fast 的步长分别为 1122,且都从头节点出发。

结论1:最终两个指针会在环中相遇,且此时慢指针 slow 还未走完环一圈。

 

证明:

设整个链表的线性部分长度为 xx,环的长度为 nn,相遇时 slow 指针在环中走了 SS 步。

假设 SnS\geq n

slow 指针总共走了 x+Sx+S 步,由于 fast 指针速度为 slow 指针2倍,所以 fast 指针走了2x+2S2x+2S 步。

slow 指针在环中走了 L(slow)=SL(slow)=S 步,fast 指针在环中走了 L(fast)=x+2SL(fast)=x+2S 步。

L(fast)L(slow)=(x+2S)S=x+S>SL(fast)-L(slow)=(x+2S)-S=x+S>S

SnS\geq n,则 L(fast)L(slow)>nL(fast)-L(slow)>n

由常识可知若两指针经过路程差大于环的长度,则两指针必定已经相遇过。

与假设矛盾,故 S<nS<n

 

那么现在已知两指针会在环中相遇,且此时慢指针还未走完一圈。

问题只剩下怎么确定环的入口。

 

设现在两指针相遇位置为 PP,则我们把 slow 指针指向链表头节点,fast 指针保持在 PP 点,但设置 fast 指针步长为 11 ,即现在两指针速度相等

 

结论2:两指针同时出发,当两个指针相遇时,相遇点即环的入口。

 

证明:

由结论1的证明可知,从环的起点走 SS 步到达 PP 点。

同样,由结论1的证明过程已知 当两指针相遇时 L(fast)L(slow)=(x+2S)S=x+SL(fast)-L(slow)=(x+2S)-S=x+S

由常识得当两指针第一次相遇时 fast 恰好超过 slow 一圈,即 L(fast)L(slow)=nL(fast)-L(slow)=n

x+S=nx+S=n------------------------①

slow 指针走到环的入口处需要 xx 步,故当 slow 指针在环的入口处时,fast 指针距离环的入口 S+xS+x 步(fast 指针步长已经被调为1),

由式①可知此时 fast 也绕完了一圈,到达环的入口。两环在环的入口处相遇。

 

代码实现(返回环的入口指针):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Node *detectCycle(Node *head) {
Node *slow = head, *fast = head;
do {
if ((fast == 0) || (fast->next == NULL)) { //链表是有限长度的,已经走到链表尾部了,说明没有环
return NULL;
}

slow = slow->next; //slow一次走一步
fast = fast->next->next; //fast一次走两步

} while (slow != fast)

for (slow = head; slow != fast; slow = slow->next, fast = fast->next); //slow拉回起点,fast从相遇点开始走都是每次直走一步直到再次相遇
return slow;
}

至于要环的长度,就新建一个tmp指向入口,一直往下走,再次走到入口返回计数器即可。