当前位置 : 首页 » 文章分类 :  算法  »  有环单链表的环长、环起点和链表长

有环单链表的环长、环起点和链表长


1、判断单链表是否有环

使用两个slow, fast指针从头开始扫描链表。指针slow 每次走1步,指针fast每次走2步。如果存在环,则指针slow、fast会相遇;如果不存在环,指针fast遇到NULL退出

就是所谓的追击相遇问题:



2、求有环单链表的环长

在环上相遇后,记录第一次相遇点为Pos,之后指针slow继续每次走1步,fast每次走2步。在下次相遇的时候fast比slow正好又多走了一圈,也就是多走的距离等于环长

设从第一次相遇到第二次相遇,设slow走了len步,则fast走了2×len步,相遇时多走了一圈:
环长=2×len-len。


3、求有环单链表的环连接点位置



    
在环上相遇后,记录第一次相遇点为Pos,连接点为Join,假设头结点到连接点的长度为LenA,连接点到第一次相遇点的长度为x,环长为R。
第一次相遇时,slow走的长度 S = LenA + x;
第一次相遇时,fast走的长度 2S = LenA + n×R + x;
所以可以知道,LenA + x = n×R;
所以LenA = n×R -x;
这个式子的意思是,第一次相遇后,如果一个指针p1从头开始走,另一个指针p2从相遇点开始走,则p1走到距离LenA处(即相遇点)时,p2走的距离为n×R -x,而n×R -x就是从相遇点绕环n圈后到环入口的距离,所以p2此时肯定也位于环入口处。
结论就是:
快慢指针第一次相遇后,一个指针从头开始以步长1前进,另一个指针继续从相遇点开始以步长1前进,则下一次相遇点就是环入口。


4、求有环单链表的链表长

上述2中求出了环的长度,3中求出了连接点的位置,也就是求出了头结点到连接点的长度,两者相加就是链表的长度。

参考:求有环单链表中的环长、环起点、链表长
https://www.cnblogs.com/xudong-bupt/p/3667729.html


上一篇 LeetCode.100.Same Tree

下一篇 MySQL-分表和表分区

阅读
541
阅读预计2分钟
创建日期 2018-02-01
修改日期 2018-02-01
类别
百度推荐