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

Question

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

Answer 1

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

最优雅的方案是：

把指针的第一个元素(呼叫他们的A和B)

然后不断循环：:

• 推进到下一个元素
• 推进到下一个元件的再次
• 提前B到下一个元素

你每次更新指针，检查，如果A和B是相同的。如果在某些时候指A和B是相同的，那么你有一个循环。该方法的问题是，你可以结束周围的环两次，但不超过两次，与指一个

如果你想要找到的元素，有两个指针指向它的，这是更加困难。我出去肢体，并说其不可能做到的只是两个指针，除非你愿意重复下面的链表一个大型的次数。

最有效的方式这样做有更多的存储器，将会把指针指向元素和列，排序，然后找一个重复。

Answer 2

<强>步骤1：继续以通常的方式，将用于发现循环，即 有两个指针，增加一个单步等两个步骤，如果他们俩的某个时候满足，有一个循环。

<强>步骤2：冻结一个指针丢失地并递增其它指针在一个步骤中计数你做出的步骤和当它们两者再次满足，则计数会给你环的长度（这是相同的计数在一个圆形链路列表中的元素的数量）。

<强>步骤3：重置两个指针到该链接列表的开始，递增一个指针的循环时间的长度，然后启动第二指示器。在一个步骤中递增两个指针，当他们再次相遇，这将是循环的开始（这是相同发现在n从链路列表的末尾^个元素）。

Answer 3

<强>数学证明+的解

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

当指针“P”将处于BEGINLOOP（即它会行进数k步骤）中，Q会行进“2K”步骤。所以，有效地，Q是提前从P '2K-K = K' 步骤时，P进入循环，因此，Q是 'N-K' 的后面BEGINLOOP现在步骤

在P会从BEGINLOOP移动到MEETPONT，它会行进“M-K”的步骤。在那个时候，Q将走过 '2（M-K）' 的步骤。但是，自从他们见面，和Q开始“N-K”的背后BEGINLOOP步骤，因此，有效的， '2（M-K） - （N-K）' 应等于 '（M-K）' 所以，

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

这意味着，在该点处等于的步骤（或多个是通用的，参见下文中提到的情况下）在循环的数目P和Q满足。现在，在MEETPOINT，p和q两者都是 'N-（M-K）' 后面的步骤，即，后面数k步骤，正如我们所看到N = M。 所以，如果我们重新开始从接头连接器P和Q从MEETPOINT但这次的步伐等于P，P和Q现在在BEGINLOOP开会而已。

常规CASE：说，K = NX + Y，Y （因此，K％N = Y）

当指针“P”将处于BEGINLOOP（即它会行进数k步骤）中，Q会行进“2K”步骤。所以，有效地，Q是提前“2K-K = K”的步骤选自P当P进入循环。但是，请注意，“K”是不是“N”，这意味着Q将做多轮循环的更大。所以，有效地，Q是 '正（K％N）' 的后面BEGINLOOP现在步骤

在P会从BEGINLOOP移动到MEETPOINT，它会行进“M-K”的步骤。 （因此，有效地，MEETPOINT将处于 '（M-K）％N' 现在提前BEGINLOOP的步骤）。在这段时间里，Q会行进 '2（M-K）' 的步骤。但是，因为它们满足，和Q开始 'N-（K％N）' 的后面BEGINLOOP步骤，所以，有效地，Q（这是“（2（MK）的位置新 - （NK /％N））％正'从BEGINLOOP）应该等于P的新的位置（这是 '（MK）％N' 从BEGIN LOOP）。

所以，

=> (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 4

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

中的继续，将使用查找循环的常规方式。即。有两个指针，递增一个在单个步骤（slowPointer）和其他在两个步骤（fastPointer），如果它们在某个时候都满足，有一个循环。

你可能会很早就意识到交汇点是循环的头前K阶。

，其中k是该列表的非环状部分的大小。

现在移动慢到循环的头

在碰撞点快速保持

每个都是从循环起始K阶（慢从列表的开始，其中作为快速是的头部前K阶环 - 画出PIC以获得清晰度）

现在以相同的速度移动他们 - 他们必须在循环开始满足

例如

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

Answer 6

这是代码，以查找在链表循环启动：

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);
}

Answer 7

有两种方式找到的循环中的一个链路清单。1.使用两个指针的一个前进的一个步骤和其他提前两个步骤，如果有的循环，在一些点都指得到同样的价值并且从来没有达到空。但是，如果没有循环指针达到空中一个点和两个指针永远不会得到同样的价值。但是，在这种方法我们可以到那里是一个循环中的链路清单，但我们不能告诉哪里开始的循环。这不是有效的方式。

2. 使用的散列函数，在这样一种方式的价值应该是独特的。这时候如果我们试图插入的重复它应该通过例外。然后通过每个节点和推动地址进入的散列。如果指针达到空和不例外，从哈希意味着不存在周期的链路清单。如果我们得到的任何异常从哈希意味着有一个周期的名单和从该周期开始。

Answer 8

那么我通过使用一个指针试图方式...我尝试的方法在几个数据集....作为每个在增加的顺序被分配的链接列表中的节点的存储器中，所以在遍历从链表的头链表，如果一个节点的地址比它指向，我们可以判断该节点的地址有环路，以及循环的开始元件大。

Answer 9

最好的回答，我们发现在这里:
tianrunhe:找到环路的起点-一个圆-连接-名单

• 'm'之间的距离头和START_LOOP
• 'L'是环长
• 'd'之间的距离MEETING_POINT和START_LOOP

• p1动至V和p2运动在2*V

  在2指满足：距离运行为=m+n*L-d=2*(m+L-d)

  =>这意味着(不mathematicaly证明这里的)，如果p1开始从头&p2开始从MEETING_POINT&他们移动，在同样的速度，他们将满足@START_LOOP

Answer 10

参考 这 完整答案的链接。

Answer 11

1. 继续以通常的方式将用来找到的循环。ie。有两个指针,增加一个在单一的步骤和其他两个步骤，如果他们满足在某个时候，有一个循环。

2. 保留一个指定获得总量的节点在循环说L.

3. 现在从这个点(增加第二个指向下一个节点在循环)在环反向链表着数量的节点走，说X

4. 现在使用的指针第二(环被破坏)从同一点在循环travrse链表着数量的节点剩余的Y说

5. 该循环开始之后((X+Y)-L)\2节点。或者，它开始在(((X+Y)-L)\2+1)th节点。

Answer 12

1. 继续以通常的方式将用来找到的循环。ie。有两个指针,增加一个在单一的步骤和其他两个步骤，如果他们满足在某个时候，有一个循环。

2. 保留一个指定获得总量的节点在循环说L.

3. 现在从这个点(增加第二个指向下一个节点在循环)在环反向链表着数量的节点走，说X

4. 现在使用的指针第二(环被破坏)从同一点在循环travrse链表着数量的节点剩余的Y说

5. 该循环开始之后((X+Y)-L)\2节点。或者，它开始在(((X+Y)-L)\2+1)th节点。

Answer 13

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);
}

Answer 14

1. 检测循环
2. 复制每个元素的地址进入设置。如果重复就是找到这就开始的循环