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

Question

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

score 164 · Accepted Answer

Step1：按照通常的方式进行，您将使用找到循环，即有两个指针，单步递增一个，另一个分两步递增，如果它们在某个时间相遇，则有一个循环。

步骤2：将一个指针冻结在原处，并在一步中增加另一个指针，计算您所做的步骤，当它们再次相遇时，计数将为您提供循环的长度（这与计算元素的数量相同循环链接列表）。

Step3：将两个指针都重置到链表的开头，将一个指针递增到循环次数的长度，然后启动第二个指针。一步递增两个指针，当它们再次相遇时，它将成为循环的开始（这与从链接列表末尾找到第 n^{个元素相同）。}

score 39 · Accepted Answer

数学证明+解决方案

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 在 BEGINLOOP 后面开始了 'nk' 步，所以，实际上，'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 在 BEGINLOOP 后面开始了 'n-(k%n)' 步，所以，实际上，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'

score 19 · Accepted Answer

首先我们尝试找出列表中是否有任何循环。如果循环存在，那么我们尝试找出循环的起点。为此，我们使用两个指针，即 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.

更多细节在这里

score 4 · Accepted Answer

Proceed in the usual way you will use to find the loop. ie. Have two pointers, increment one in single step(slowPointer) and other in two steps(fastPointer), If they both meet in sometime, there is a loop.

As you might would have already realized that meeting point is k Step before the head of the loop.

where k is size of non-looped part of the list.

now move slow to head of the loop

keep Fast at collision point

each of them are k STep from the loop start (Slow from start of the list where as fast is k step before the head of the loop- Draw the pic to get the clarity)

Now move them at same speed - They must meet at loop start

eg

slow=head
while (slow!=fast)
{
     slow=slow.next;
     fast=fast.next;
}

score 4 · Accepted Answer

这是在链表中查找循环开始的代码：

public static void findStartOfLoop(Node n) {

    Node fast, slow;
    fast = slow = n;
    do {
        fast = fast.next.next;
        slow = slow.next;
    } while (fast != slow);       

    fast = n;
    do {
        fast = fast.next;
        slow = slow.next;
    }while (fast != slow);

    System.out.println(" Start of Loop : " + fast.v);
}

score 1 · Accepted Answer

有两种方法可以在链接列表中找到循环。1.如果有循环，使用两个指针一个前进一步，另一个前进两步，在某些时候两个指针都得到相同的值并且永远不会达到空值。但是，如果没有循环指针在某一点达到 null 并且两个指针永远不会获得相同的值。但是在这种方法中，我们可以在链接列表中找到一个循环，但我们无法确定循环的确切开始位置。这也不是有效的方法。

以这样的方式使用散列函数，使得值应该是唯一的。如果我们试图插入副本，它应该通过异常。然后遍历每个节点并将地址推送到哈希中。如果指针达到 null 并且哈希没有异常意味着链接列表中没有循环。如果我们从哈希中得到任何异常，则意味着列表中有一个循环，这就是循环开始的链接。

score 1 · Accepted Answer

好吧，我尝试了一种使用一个指针的方法……我在几个数据集中尝试了该方法……由于链表的每个节点的内存都是按递增顺序分配的，因此在从链表的头部，如果一个节点的地址变得大于它所指向的节点的地址，我们可以确定有一个循环，以及循环的开始元素。

score 1 · Accepted Answer

我找到的最佳答案在这里：
tianrunhe: find-loop-starting-point-in-a-circular-linked-list

'm' 是 HEAD 和 START_LOOP 之间的距离
'L' 是循环长度
'd' 是 MEETING_POINT 和 START_LOOP 之间的距离
p1 在 V 处移动，p2 在 2*V 处移动

当 2 个指针相遇时：跑步距离 = m+ n*L -d = 2*(m+ L -d)
=> 这意味着（此处未在数学上证明）如果 p1 从 HEAD 开始 & p2 从 MEETING_POINT 开始并且它们以相同的速度移动，它们将遇到@START_LOOP

score 1 · Accepted Answer

1

请参阅此链接以获取全面的答案。

于 2013-08-23T10:18:41.077 回答

score 0 · Accepted Answer

以您将用于查找循环的常用方式继续。IE。有两个指针，一个单步递增，另一个分两步递增，如果它们在某个时间相遇，则有一个循环。
保持其中一个指针固定得到循环中的节点总数，比如 L。
现在从这一点开始（增加第二个指向循环中下一个节点的指针）在循环中反转链表并计算遍历的节点数，比如 X。
现在使用循环中同一点的第二个指针（循环被破坏）遍历链表并计算剩余的节点数说 Y
循环在 ((X+Y)-L)\2 节点之后开始。或者它从第 (((X+Y)-L)\2+1) 个节点开始。

score 0 · Accepted Answer

以您将用于查找循环的常用方式继续。IE。有两个指针，一个单步递增，另一个分两步递增，如果它们在某个时间相遇，则有一个循环。
保持其中一个指针固定得到循环中的节点总数，比如 L。
现在从这一点开始（增加第二个指向循环中下一个节点的指针）在循环中反转链表并计算遍历的节点数，比如 X。
现在使用循环中同一点的第二个指针（循环被破坏）遍历链表并计算剩余的节点数说 Y
循环在 ((X+Y)-L)\2 节点之后开始。或者它从第 (((X+Y)-L)\2+1) 个节点开始。

score 0 · Accepted Answer

拿两个指针，一个快，一个慢。慢指针一次移动一个节点，快速指针一次移动两个节点，最终它们会相遇，你会找到循环。
现在到了有趣的部分，你如何检测循环？这也很简单。让我先问你另一个有趣的问题：你将如何一次搜索列表中的 nx 节点？简单的答案是取两个指针，一个在头部，一个在头部前面 x 步处，并以相同的速度移动它们，当第二个指针到达终点时，第一个将在 nx 处。
正如许多其他人在该线程中以数学方式证明的那样，如果一个指针的移动速度是一个指针的两倍，则从起点到它们相遇的点的距离将是列表长度的倍数。为什么会这样？？由于快指针的移动速度是慢指针的两倍，我们是否可以同意：快指针经过的距离 = 2 *（慢指针经过的距离）

现在：

如果 m 是没有循环的循环的长度（循环中的节点）
如果 n 是循环的实际长度。
x 是慢指针的周期数
y 是快速指针的周期数。
K 是从循环起点到交汇点的距离
请注意，这一点是两个指针路径中唯一的一段长度，在它们的循环周期数之后将变得额外。因此，除了这 k 个其余部分之外，还有循环的周期以及从头部到循环开始的初始距离。因此，在他们相遇的循环之后，两人都在旅行 m+n*（他们所做的循环数）+ k 距离。所以，我们可以这样说：

(m + n x + k) = 2 (m + n*y + k)
当你用数学方法解决这个问题时，你会发现 m+k 是循环长度的倍数，即 nie [m + k = (x-2y)*n]
所以，如果你保持一段长度的距离并最终移动，你会在循环开始时再次相遇。为什么？他们不能在别的地方见面吗？好吧，快已经在 k 处，而慢则在头部，如果它们都行进 m 距离，因为 k + m 是 n 的倍数，那么快将在循环的开始。而如果慢速行驶 m 距离，它将遇到 k，因为 m 是从头到循环起点的距离，正如我们最初假设的 m 那样。
因此，从数学上证明，如果在检测到循环后再次将慢速指针设置为 head 并使它们以相同的速度移动，则快速和慢速指针都必须移动的距离为 m。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null||head.next==null)return null;
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next!=null&&fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(fast==slow){
                slow=head;
                while(slow!=fast){
                    slow=slow.next;
                    fast=fast.next;
                }
                return slow;
            }
        }
        return null;
    }
}

score 0 · Accepted Answer

基于@hrishikeshmishra 解决方案的Pythonic 代码解决方案

def check_loop_index(head):
    if head == None or head.next == None:
        return -1
    
    slow = head.next
    if head.next.next == None:
        return  -1
    fast = head.next.next
    
    # searching for  loops exists or not
    while fast and fast.next:
        if slow==fast:
            break
        slow = slow.next
        fast = fast.next.next
    
    # checking if there is loop 
    if slow != fast:
        return -1
    
    # reseting the slow to head and creating index
    index = 0
    slow = head
    
    # incrementing slow and fast by 1 step and incrmeenting index, if they meet 
    # hen thats the index of node where loop starts
    while slow!=fast:
        slow = slow.next
        fast = fast.next
        index+=1

    return index

score 0 · Accepted Answer

void loopstartpoint(Node head){
    Node slow = head.next;;
    Node fast = head.next.next;

    while(fast!=null && fast.next!=null){
        slow = slow.next;
        fast = fast.next.next;

        if(slow==fast){
            System.out.println("Detected loop ");
            break;
        }
    }

    slow=head;
    while(slow!=fast){
        slow= slow.next;
        fast = fast.next;
    }
    System.out.println("Starting position of loop is "+slow.data);
}

score -2 · Accepted Answer

检测回路
将每个元素的地址复制到集合中。如果发现重复，那就是循环的开始

score -4 · Accepted Answer

我听说过这个确切的问题作为面试测验问题。

最优雅的解决方案是：

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

然后继续循环::

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

每次更新指针时，检查 A 和 B 是否相同。如果在某些时候指针 A 和 B 是相同的，那么你有一个循环。这种方法的问题是您最终可能会在循环中移动两次，但使用指针 A 不超过两次

如果你想真正找到有两个指针指向它的元素，那就更难了。除非您愿意多次重复链接列表，否则我会竭尽全力说仅使用两个指针是不可能的。

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

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

16 回答 16

Related

Reference