-1

我必须在使用海龟和野兔解决方案发现的链表中找出循环，如下所示

boolean hasLoop(Node first) {

    if(first == null) // list does not exist..so no loop either.
        return false;

    Node slow, fast; // create two references.

    slow = fast = first; // make both refer to the start of the list.

    while(true) {

        slow = slow.next;          // 1 hop.

        if(fast.next != null)
            fast = fast.next.next; // 2 hops.
        else
            return false;          // next node null => no loop.

        if(slow == null || fast == null) // if either hits null..no loop.
            return false;

        if(slow == fast) // if the two ever meet...we must have a loop.
            return true;
    }
}

现在我的问题是如何检测循环的开始以及如何计算程序的复杂性，就好像我增加了列表的大小一样。指针相交的点在列表大小中的比例不会增加。

4

2 回答 2

1

从破解编码采访：

想象一下，作为一个类比，两个人在赛道上比赛，一个人跑的速度是另一个人的两倍。如果他们从同一个地方出发，他们下一次见面是什么时候？他们将在下一圈开始时相遇。

现在，让我们假设 Fast Runner 在 n 步的圈速上领先 k 米。他们下次见面什么时候？他们将在下一圈开始前相遇公里。（为什么？Fast Runner 会走 k + 2(n - k) 步，包括它的领先优势，Slow Runner 会走 n - k 步。两者都是循环开始前的 k 步。）

现在，回到问题，当 Fast Runner (n2) 和 Slow Runner (n1) 在我们的循环链表中移动时，当 n1 进入时，n2 将在循环中领先。具体来说，它将具有 k 的领先优势，其中 k 是循环之前的节点数。由于 n2 有 k 个节点的领先起点，因此 n1 和 n2 将在循环开始之前遇到 k 个节点。

所以，我们现在知道以下内容：

  1. Head 是来自 LoopStart 的 k 个节点（根据定义）。
  2. n1 和 n2 的 MeetingPoint 是来自 LoopStart 的 k 个节点（如上所示）。

因此，如果我们将 n1 移回 Head 并将 n2 保持在 MeetingPoint，并以相同的速度移动它们，它们将在 LoopStart 相遇。

LinkedListNode FindBeginning(LinkedListNode head) 
{
    LinkedListNode n1 = head;
    LinkedListNode n2 = head;
    // Find meeting point
    while (n2.next != null) 
    {
        n1 = n1.next;
        n2 = n2.next.next;
        if (n1 == n2) 
        {
            break;
        }
    }

     // Error check - there is no meeting point, and therefore no loop
     if (n2.next == null) 
     {
        return null;
     }

    /* Move n1 to Head. Keep n2 at Meeting Point. Each are k steps
    /* from the Loop Start. If they move at the same pace, they must
    * meet at Loop Start. */
    n1 = head;
    while (n1 != n2) 
    {
        n1 = n1.next;
        n2 = n2.next;
    }
    // Now n2 points to the start of the loop.
    return n2;
}
于 2013-10-19T07:57:56.633 回答
0

如果没有循环，那么您的代码将执行，Θ(n)因为您至少跳n多次且最多跳3/2*n。

如果有一个循环，那么在图论中它最多是一个长度为 的循环n。循环之间的距离fast和slow循环上的距离完全1随着每一跳而变化，因此它们在大多数n时候都在进入循环直到它们相遇之后才跳跃。它们都在最多n-1跳数之后进入循环，因此这会给您带来2*(n-1) + 2*n ∈ O(n)最坏情况的复杂性。

[循环的最佳情况复杂性是O(1)因为您可以立即进入循环，这意味着在恒定数量的跃点之后，所以这不是很有趣。]

于 2013-10-19T11:48:10.577 回答