GG.*_*GG. 51 algorithm linked-list cycle data-structures floyd-cycle-finding
我已经看过一个问题,讨论在链表中查找循环的算法.我已经阅读了Floyd的循环寻找算法解决方案,在许多地方提到我们必须采取两个指针.一个指针(慢/龟)增加一个,其他指针(更快/野兔)增加2.当它们相等时我们找到循环,如果更快的指针到达null,则链表中没有循环.
现在我的问题是为什么我们将指针增加更快2.为什么不是别的呢？增加2是必要的,或者我们可以将它增加X来得到结果.如果我们将指针增加2,或者可能存在需要增加3或5或x的情况,我们是否有必要找到一个循环.
tem*_*def 52
你没有理由需要使用二号.任何步长选择都可行(当然除了一个).
为了了解其工作原理,让我们先来看看为什么Floyd的算法起作用.想法是考虑列表的开头,然后从列表的开头然后访问的链接列表的元素的序列x 0,x 1,x 2,...,x n,...继续往下走,直到你到达终点.如果列表不包含循环,则所有这些值都是不同的.但是,如果它确实包含一个循环,那么这个序列将无休止地重复.
这是使Floyd算法工作的定理:
链接列表包含一个周期当且仅当有一个正整数j,使得对于任何正整数k,X Ĵ = X JK.
我们来证明这一点; 这并不难.对于"if"情况,如果存在这样的aj,则选择k = 2.然后我们得到一些正j,x j = x 2j和j≠2j,因此列表包含一个循环.
对于另一个方向,假设列表包含从位置s开始的长度为l的循环.设j是l大于s的最小倍数.然后对于任何k,如果我们考虑x j和x jk,因为j是循环长度的倍数,我们可以将x jk视为通过从列表中的位置j开始形成的元素,然后采用j步k-1倍.但是每次你采取j步,你最后都会回到你在列表中开始的位置,因为j是循环长度的倍数.因此,x j = x jk.
这个证明可以保证,如果你在每次迭代中采用任意数量的步骤,你确实会遇到慢速指针.更确切地说,如果你在每次迭代中采取k步,那么你最终将找到点x j和x kj并将检测周期.直观地,人们倾向于选择k = 2来最小化运行时间,因为在每次迭代时采用最少的步数.
我们可以更正式地分析运行时,如下所示.如果列表不包含循环,则快速指针将在n(n)次的n步之后到达列表的末尾,其中n是列表中的元素数.否则,在慢速指针采取j步之后,两个指针将会相遇.请记住,j是l大于s的最小倍数.如果s≤l,则j = 1; 否则如果s> l,则j最多为2s,因此j的值为O(s + 1).由于l和s可以不大于列表中元素的数量,这意味着比j = O(n).但是,在慢速指针经过j步之后,快速指针将对较慢指针所采用的每个j步进行k步,因此它将采取O(kj)步.由于j = O(n),净运行时间最多为O(nk).请注意,这表示我们使用快速指针执行的步骤越多,算法完成所需的时间越长(尽管只是按比例).挑选k = 2因此最小化算法的整体运行时间.
希望这可以帮助!
Sum*_*Das 34
让我们假设该列表的长度不包含循环中s,循环的长度t和比例fast_pointer_speed来slow_pointer_speed是k.
让两个指针在距j循环开始一段距离处相遇.
所以,距离慢指针移动= s + j.快速指针行进的距离= s + j + m * t(其中m是快速指针完成循环的次数).但是,快速指针也会移动一段距离k * (s + j) (k慢指针的距离).
因此,我们得到k * (s + j) = s + j + m * t.
s + j = (m / k-1)t.
因此,根据上面的等式,慢指针行进的长度是循环长度的整数倍.
为了获得最大效率,(m / k-1) = 1(慢指针不应该多次遍历循环.)
因此, m = k - 1 => k = m + 1
由于m快速指针已经完成循环的次数,m >= 1.为了最大的效率,m = 1.
因此k = 2.
如果我们取值k > 2,那么两个指针必须移动的距离越多.
希望以上解释有所帮助.
考虑大小为L的循环,意味着在第k个元素处是循环所在的位置:x k - > x k + 1 - > ... - > x k + L-1 - > x k.假设一个指针以r 1 = 1的速率运行而另一个指针以r 2运行.当第一个指针到达x k时,第二个指针已经在某个元素x k + s的循环中,其中0 <= s <L.在m进一步指针递增后,第一个指针位于x k +(m mod L)并且第二个指针位于x k +((m*r 2 + s)mod L).因此,两个指针碰撞的条件可以表达为满足一致性的m的存在
m = m*r 2 + s(mod L)
这可以通过以下步骤简化
m(1-r 2)= s(mod L)
m(L + 1-r 2)= s(mod L)
这是线性同余的形式.如果s可被gcd(L + 1-r 2,L)整除,则它有一个解.如果gcd(L + 1-r 2,L)= 1,肯定会出现这种情况.如果r 2 = 2则gcd(L + 1-r 2,L)= gcd(L-1,L)= 1并且总是存在解m.
因此,r 2 = 2具有良好的性质,对于任何周期大小L,它满足gcd(L + 1-r 2,L)= 1并因此保证即使两个指针在不同位置开始,指针也将最终发生碰撞.r 2的其他值不具有此属性.
如果快指针移动3步而慢指针在1步上移动，则不能保证两个指针在包含偶数个节点的循环中相遇。2但是，如果慢速指针逐步移动，则会议将得到保证。
一般来说，如果兔子一步步移动H，乌龟T一步一步移动，你肯定会在一个循环中相遇 iff H = T + 1。
考虑兔子相对于乌龟移动。
H - T每次迭代的节点数。给定一个长度为 的循环N =(H - T) * k，其中k是任何正整数，野兔会跳过每个H - T - 1节点（同样，相对于乌龟），如果乌龟在这些节点中的任何一个，它们就不可能相遇。
保证会议的唯一可能性是何时H - T - 1 = 0。
因此，x允许将快指针增加，只要慢指针增加x - 1。
这是一种直观的非数学方式来理解这一点：
如果快速指针超出链表末尾，则显然不存在循环。
忽略指针位于链表初始非循环部分的初始部分，我们只需要把它们放入循环即可。当慢指针最终到达循环时，快指针在循环中的位置并不重要。
一旦它们都进入循环，它们就会围绕循环运行，但在不同的点上。想象一下，如果它们每次都移动一格。然后他们会绕着自行车转一圈，但保持相同的距离。换句话说，进行相同的循环但异相。现在，通过将快速指针每移动两步，它们就会彼此改变相位；每走一步，彼此的距离就减少一分。快指针将追上慢指针，我们可以检测到循环。
为了证明这是真的，它们会相遇，并且快指针不会以某种方式超越并跳过慢指针，只需手动模拟当快指针落后慢指针三步时会发生什么，然后模拟当快指针落后慢指针时会发生什么落后慢速两步，则当快指针仅落后慢速指针一步时。在每种情况下，它们都在同一节点相遇。任何更大的距离最终都会变成三、二或一的距离。
编辑：如果快指针移动了 3、4 或 5，那么快指针有可能“跳过”慢指针，而不会击中同一个节点。