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

问题描述 投票：24回答：14

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

loops linked-list find singly-linked-list cycle-detection
14个回答
0
投票

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

最优雅的解决方案是：

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

然后继续循环::

  • 将A推进到下一个元素
  • 再次将A推进到下一个元素
  • 将B推进到下一个元素
Every time you update a pointer, check if A and B are identical. If at some point pointers A and B are identical, then you have a loop. Problem with this approach is that you may end up moving around the loop twice, but no more than twice with pointer A

如果你想真正找到有两个指向它的指针的元素，那就更难了。除非你愿意多次重复关注链表，否则我只能用两个指针说不可能做到这一点。

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

1
投票

有关综合答案，请参阅this链接。

0
投票
  1. 按照通常的方式继续查找循环。即。有两个指针，一步递增一步，两步递增，如果它们在某个时间相遇，则有一个循环。
  2. 保持其中一个指针固定得到循环中的节点总数说L.
  3. 现在从这一点（在循环中递增指向循环中下一个节点的第二个指针）反转链表并计算遍历的节点数，比如说X.
  4. 现在使用第二个指针（循环被破坏）从循环中的同一点遍历链表并计算剩余的节点数量Y
  5. 循环在（（X + Y）-L）\ 2节点之后开始。或者它从（（（X + Y）-L）\ 2 + 1）节点开始。
0
投票
  1. 按照通常的方式继续查找循环。即。有两个指针，一步递增一步，两步递增，如果它们在某个时间相遇，则有一个循环。
  2. 保持其中一个指针固定得到循环中的节点总数说L.
  3. 现在从这一点（在循环中递增指向循环中下一个节点的第二个指针）反转链表并计算遍历的节点数，比如说X.
  4. 现在使用第二个指针（循环被破坏）从循环中的同一点遍历链表并计算剩余的节点数量Y
  5. 循环在（（X + Y）-L）\ 2节点之后开始。或者它从（（（X + Y）-L）\ 2 + 1）节点开始。
0
投票
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);
}
-2
投票
  1. 检测循环
  2. 将每个元素的地址复制到集合中。如果发现重复是循环的开始
122
投票

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

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

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

28
投票

数学证明+解决方案

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后面的'n-k'步。

当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。所以，如果我们再次从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时，它会走“m-k”步。 （因此，有效的是，MEETPOINT现在比BEGINLOOP先行'（m-k）％n'步骤。）在那个时候，Q将会走“2（m-k）”步。但是，既然他们遇到了，并且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'
12
投票

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

enter image description here

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.

More detail here

4
投票

按照通常的方式继续查找循环。即。有两个指针，一步递增一个（slowPointer），另一个递增两步（fastPointer），如果它们在某个时间相遇，则有一个循环。

正如您可能已经意识到会合点是k循环前的步骤。

其中k是列表的非循环部分的大小。

现在慢慢转到循环的头部

保持快速碰撞点

它们中的每一个都是从循环开始的k STep（从列表的开始开始缓慢，其中在循环的头部之前快速为k步 - 绘制图片以获得清晰度）

现在以相同的速度移动它们 - 它们必须在循环开始时相遇

例如

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

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

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);
}
1
投票

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

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

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

1
投票

我找到的最佳答案是： 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
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.