如果环前面的链表很长,而环短,那么快指针进入环以后可能转了好几圈才和慢指针相遇。但无论如何,慢指针在进入环的第一圈的时候就会和快的相遇。假设环长是s,(a+b)*2=a+n*s+b 可以得出a+b=n*s 。 现在新建一个slow2的指针指向头结点,原来的slow指针依旧停留在相遇点p。接下来他们都以一次走一个位置的速度往前走。为什么当slow2走完a路程到入口节点处会和slow指针相遇呢? 因为通过a+b=n*s,可以推出a= n*s-b 。它正好对应slow指针走的路径长度。
1

相关推荐

头像
11-07 01:12
重庆大学 Java
精致的小松鼠人狠话不多:签哪了哥
点赞 评论 收藏
分享
11-04 14:10
东南大学 Java
_可乐多加冰_:去市公司包卖卡的
点赞 评论 收藏
分享
牛客网
牛客企业服务