在 Java 中打破 linkedlist 中的循环并发现复杂性

Question

我必须找出链表中的循环，这是我使用和野兔解决方案发现

的，如下所示

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

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

Answer 1

来自 破解编码面试：

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

现在，让我们假设 Fast Runner 在 n 步圈中领先 k 米。他们下次见面是什么时候？他们将在下一圈开始前遇到 k 米。（为什么？Fast Runner 会做 k + 2（n - k） 步，包括它的领先一步，而 Slow Runner 会做 n - k 步。两者都将是循环开始前的 k 步。

现在，回到问题，当快速运行者（n2）和慢速运行者（n1）在我们的循环链表中移动时，当n1进入时，n2将在循环中领先一步。具体来说，它将有一个 k 的领先优势，其中 k 是循环前的节点数。由于 n2 有 k 个节点的领先优势，n1 和 n2 将在循环开始之前满足 k 个节点。

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

1. 头部是来自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;
}

Answer 2

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

如果存在循环，那么在图论术语中，它最多是一个长度n的循环。循环中fast和slow之间的距离随着每个跳跃而变化1，因此它们在进入循环后最多跳n次，直到相遇。它们在最多 n-1 个跃点后进入循环，因此这为您提供了2*(n-1) + 2*n ∈ O(n)最坏的情况复杂性。

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