天天看点

单链表的环相关问题

给定一个单链表,只给出头指针h:

1、 如何判断是否存在环?

证明:

单链表的环相关问题

 slow首次在a点进入环路时,fast一定在环中的b点某处。设此时slow距head长为x,b点距a点长度为y,环周长为s。因为fast和slow的步差为1,所以slow前行距离为y的时候,恰好会被fast在m点追上。因为y<s,所以slow尚未完成一次遍历。

2、 如何知道环的长度?

证明:(有公式所以截图了)

单链表的环相关问题

3、 如何找出环的连接点在哪里?

证明:在fast和slow第一次相遇的时候,假定slow走了n步骤,环路的入口是在x步的时候经过的,那么有

slow走的路径: x+y = n;   y为fast和slow相交点m距离环路入口的距离

fast走的路径: x+y+k*s = 2*n;   s为环路的周长,k是整数

所以得出 n = k*s;

显然,如果从x+y点开始,slow再走n步的话,还可以回到x+y这个点(绕了k圈)

同时另一个指针temp从头开始走的话,经过n步,也会达到x+y这点

两者都减去y步,可知两者走x步必然会在环路的入口点处相遇

4、带环链表的长度是多少?

证明:总长度 = s + x;

继续阅读