首页 > 其他 > 详细

【单链表】找出单链表中环的“入口”

时间:2015-03-16 12:56:26      阅读:363      评论:0      收藏:0      [点我收藏+]

题目:

    找出单链表中环的“入口”。

    

解答步骤:

1、用快慢指针判断是否存在环(慢指针走一步,快指针走两步)。若存在环则继续下面的计算,若不存在则返回nullptr;

2、记录快慢指针相遇的节点n0.

3、一个指针从链表头结点出发,另一个指针从n0出发,“同步前进”,相遇的节点就是环的“入口”。


分析:

由于快慢指针所走的“步数”相同,但快指针每一步是慢指针的两倍,所以快慢指针在n0相遇时,快指针所走距离是慢指针的两倍,即:

S=Length+Ns*R+s0                          (1)

2S=Lengh+Nf*R+s0                          (2)

上式中,S是慢指针所走距离,R是环的长度,s0是环入口到n0的距离,Ns是慢指针在环中绕的圈数,Nf是快指针在环中绕的圈数。

(2)式减(1)式,可得

S=(Nf-Ns)*R,其中Nf>Ns

可见S是R的倍数!假设S=k*R,k是一个正整数,代入(1)式可得

Length+s0=(k-Ns)*R,令j= k-Ns,j是一个正整数。

可见Length+s0也是R的倍数!已知节点n0到环入口的距离为R-s0,Length=j*R-s0.

令一个指针从链表头结点出发,另一个指针从n0出发,“同步前进”,必然会在某个节点相遇。当j=1时,Length=R-s0,显然相遇节点就是环入口。当j>1时,仍然在环入口相遇,想想为什么?

【单链表】找出单链表中环的“入口”

原文:http://blog.csdn.net/bupt8846/article/details/44303115

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!