检测单链接链表中循环的开始？

Question

是否有任何方法可以使用不超过两个指针找到链接列表中的循环开始？ 我不想访问每个节点并标记它并报告第一个节点已经被看到.有没有其他方法可以做到这一点？

Answer 1

Step1:以通常的方式继续,你将用来找到循环,即有两个指针,在一步中递增一个,在另外两个步骤中递增,如果它们在某个时间相遇,则有一个循环.

Step2:将一个指针冻结到原来的位置,然后在一步计数中增加另一个指针,计算你所做的步骤,当它们再次相遇时,计数将给你循环的长度(这与计算一个元素的数量相同)循环链接列表).

步骤3:重置指向链接列表开头的两个指针,将一个指针递增到循环次数的长度,然后启动第二个指针.在一步中递增两个指针,当它们再次相遇时,它将是循环的开始(这与从链接列表的末尾查找第n ^个元素相同).

Answer 2

数学证明+解决方案

Let 'k' be the number of steps from HEADER to BEGINLOOP.
Let 'm' be the number of steps from HEADER to MEETPOINT.
Let 'n' be the number of steps in the loop.
Also, consider two pointers 'P' and 'Q'. Q having 2x speed than P.

简单案例:当k <N时

当指针'P'处于BEGINLOOP时(即它将经过'k'步),Q将走"2k"步.因此,当P进入循环时,Q有效地从P开始'2k-k = k'步,因此,Q现在是BEGINLOOP后面的'nk'步.

当P从BEGINLOOP转移到MEETPONT时,它会走"mk"步.在那个时候,Q将会走"2(mk)"步.但是,既然他们遇到了,Q开始'nk'步骤落后于BEGINLOOP,那么,实际上,'2(mk) - (nk)'应该等于'(mk)'所以,

=> 2m - 2k - n + k = m - k
=> 2m - n = m
=> n = m

这意味着,P和Q在等于循环中的步数(或多个一般,见下面提到的情况)的点处相遇.现在,在MEETPOINT,P和Q都是'n-(mk)'后面的步骤,即'k'步后面,我们看到n = m.所以,如果我们再次从HEADER开始P,从MEETPOINT开始Q,但这次的速度等于P,P和Q现在只在BEGINLOOP开会.

一般情况:比方说,k = nX + Y,Y <n (因此,k%n = Y)

当指针'P'处于BEGINLOOP时(即它将经过'k'步),Q将走"2k"步.因此,当P进入循环时,Q有效地从P开始'2k-k = k'步.但是,请注意'k'大于'n',这意味着Q将进行多轮循环.因此,有效地,Q现在是BEGINLOOP后面的'n-(k%n)'步骤.

当P从BEGINLOOP转移到MEETPOINT时,它会走"mk"步.(因此,有效的是,MEETPOINT现在比BEGINLOOP先行'(mk)%n'步骤.)在那个时候,Q将走"2(mk)"步.但是,既然他们遇到了,并且Q开始'n-(k%n)'步骤落后于BEGINLOOP,那么,实际上,Q的新位置(即'(2(mk) - (nk /%n))%n '来自BEGINLOOP)应该等于P的新位置(来自BEGIN LOOP的'(mk)%n').

所以,

=> (2(m - k) - (n - k%n))%n = (m - k)%n
=> (2(m - k) - (n - k%n))%n = m%n - k%n
=> (2(m - k) - (n - Y))%n = m%n - Y   (as k%n = Y)
=> 2m%n - 2k%n - n%n + Y%n = m%n - Y
=> 2m%n - Y - 0 + Y = m%n - Y    (Y%n = Y as Y < n)
=> m%n = 0
=> 'm' should be multiple of 'n'

Answer 3

首先我们试着找出,列表中是否有任何循环.如果循环存在,那么我们试图找出循环的起点.为此,我们使用两个指针,即slowPtr和fastPtr.在第一次检测(检查循环)时,fastPtr一次移动两步,但slowPtr一次向前移动一步.

slowPtr   1   2   3   4   5   6   7
fastPtr   1   3   5   7   9   5   7

很明显,如果列表中有任何循环,那么它们将在点(上图中的点7)处相遇,因为fastPtr指针的运行速度比其他指针快两倍.

现在,我们来找到寻找循环起点的第二个问题.

假设他们在第7点见面(如上图所示).然后,slowPtr退出循环并且位于列表的开头意味着在第1点但是fastPtr仍然在会合点(第7点).现在我们比较两个指针值,如果它们相同则它是循环的起点,否则我们向前移动一步(这里fastPtr每次也移动一步)并再次比较直到我们找到相同的点.

slowPtr   1   2   3   4
fastPtr   7   8   9   4

现在有一个问题,它是如何可能的.所以有很好的数学证明.

假设:

m => length from starting of list to starting of loop (i.e 1-2-3-4)
l => length of loop (i.e. 4-5-6-7-8-9)
k => length between starting of loop to meeting point (i.e. 4-5-6-7)

Total distance traveled by slowPtr = m + p(l) +k
where p => number of repetition of circle covered by slowPtr

Total distance traveled by fastPtr = m + q(l) + k
where q => number of repetition of circle covered by fastPtr

Since,
fastPtr running twice faster than slowPtr

Hence,
Total distance traveled by fastPtr = 2 X Total distance traveled by slowPtr
i.e
m + q(l) + k = 2 * ( m + p(l) +k )
or, m + k = q(l) - p(l)
or, m + k = (q-p) l
or, m = (q-p) l - k

So,
If slowPtr starts from beginning of list and travels "m" length then, it will reach to Point 4 (i.e. 1-2-3-4)

and
fastPtr start from Point 7 and travels " (q-p) l - k " length then, it will reach to Point 4 (i.e. 7-8-9-4),
because "(q-p) l" is a complete circle length with " (q-p) " times.

更多细节在这里

Answer 4

我在面试测验中听到过这个确切的问题。

最优雅的解决方案是：

将两个指针放在第一个元素上（称它们为 A 和 B）

然后继续循环::

• 将 A 前进到下一个元素
• A 再次前进到下一个元素
• 将 B 前进到下一个元素

每次更新指针时，检查 A 和 B 是否相同。如果在某个时刻指针 A 和 B 相同，则存在循环。这种方法的问题在于，您最终可能会在循环中移动两次，但指针 A 的次数不会超过两次

如果你想真正找到有两个指针指向它的元素，那就更困难了。我会大胆地说，仅用两个指针是不可能做到的，除非您愿意多次重复遵循链表。

使用更多内存执行此操作的最有效方法是将指针放入数组中的元素，对其进行排序，然后查找重复项。