Aiur · Zellux 的博客
blog.yxwang.me
很经典的问题了，求环的长度可以用两个步长分别为1和2的指针遍历链表，直到两者相遇。相遇后把其中指针重新设定为起始点，让两个指针以步长1再走一遍链表，相遇点就是环的起始点。 证明也很简单，注意第一次相遇时 慢指针走过的路程S1 = 非环部分长度 + 弧A长 快指针走过的路程S2 = 非环部分长度 + n * 环长 + 弧A长 S1 * 2 = S2，可得非环部分长度 = n * 环长 - 弧A长 指…
讨论
登录后参与讨论
还没有评论，来说第一句吧。