给定一个单链表
1. 如何判断链表是否存在环?
2. 如何知道环的长度?
3. 如何找出环的连接点在哪里?
4. 带环链表的长度?
解法:
1. 对于问题1
使用追赶的方法,设定两个指针show,fast,从头节点开始,每次分别前进1步,2步,如存在环则两者必然会相遇,如不存在环,则fast遇到null退出,并且碰撞点到头节点的距离为环中节点数n.
2. 对于问题2:
记录下问题1的碰撞点p,碰撞点p肯定是在环中的,从这个节点触发,一边移动一边计数再次回到这个节点就得到了环中节点数n
3. 对于问题3:
有定理: 碰撞点p到连接点的距离=头节点到连接点的距离,因此分别从碰撞点,头节点相同速度开始走相遇的那个点就是连接点.
定理证明如下:
设头节点到连接点的距离为x,连接点到碰撞点的距离为y,碰撞点到连接点的距离为z,环的长度为n,
(1) 碰撞点到头节点的距离为n,则有x+y=n
(2) 又因为环的长度为n,则有y+z=n
(3) 由(1),(2) 可得,碰撞点p到连接点的距离=头节点到连接点的距离
4. 对于问题4
问题3中已经求出连接点距离头指针的长度,加上问题2中求出的环的长度,二者之和就是带环链表的长度.
