2
带环链表求环的起点
source link: https://blog.yxwang.me/2008/09/find-head-in-circular-linked-list/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
带环链表求环的起点
Mon, Sep 8, 2008 • Algorithms
很经典的问题了，求环的长度可以用两个步长分别为1和2的指针遍历链表，直到两者相遇。相遇后把其中指针重新设定为起始点，让两个指针以步长1再走一遍链表，相遇点就是环的起始点。
证明也很简单，注意第一次相遇时
慢指针走过的路程S1 = 非环部分长度 + 弧A长
快指针走过的路程S2 = 非环部分长度 + n * 环长 + 弧A长
S1 * 2 = S2，可得非环部分长度 = n * 环长 - 弧A长
指针A回到起始点后，走过一个非环部分长度，指针B走过了相等的长度，也就是n * 环长 - 弧A长，正好回到环的开头。
本作品采用知识共享署名-非商业性使用 3.0 版本许可协议进行许可，欢迎转载，演绎，但是必须保留本文的署名 zellux（包含链接），且不得用于商业目的。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK