循环链表算法

Question

最近在一次工作面试中，我被要求开发一个算法来确定一个链表是否是循环的。由于它是一个链表，我们不知道它的大小。它是一个双向链表，每个节点都有“next”和“previous”指针。一个节点可以连接到任何其他节点，也可以连接到自身。

那时我想到的唯一解决方案是选择一个节点并将其与链表中的所有节点进行检查。显然，面试官并不喜欢这个想法，因为它不是一个最优解。有什么更好的方法吗？

- Taimur Ajmal

---

这和https://dev59.com/cUnSa4cB1Zd3GeqPNmiq是一样的吗？ - AnthonyLambert

你的原始解决方案并不是一个真正的解决方案，因为如果你选择了圆形外的节点，你的解决方案将会进入无限循环。这远非“最优解”。通常在面试中，即使是一个糟糕的解决方案，只要它是一个解决方案，也是可以接受的。 - Codism

你想要检查整个列表是否是循环的，还是列表内部存在某些循环？ - bta

我讨厌这种面试问题。如果有人知道答案，那只能说明他们知道答案。如果他们不知道“正确”的答案，他们该如何找出来呢？靠瞎猜？哼。我听说过这个问题被问成“如何找到链表的中间节点？”这与一些面试问题的解法和问题是相同的。我认为这些被称为“啊哈！”问题，在 SO 播客的过去几集中也提到过。 - Carl Norum

@Codism: 我认为假设是他从列表中选择了一个节点，然后遍历该列表直到找到它或结束（NULL ptr）。然后他就会知道。 - nategoose

Answer 1

你需要的是一个循环查找算法。Joel提到的算法称为“乌龟和兔子”算法或Floyd的循环查找算法。我更喜欢后者，因为它听起来像是一个很好的D&D咒语。 循环查找算法维基百科概述，带有示例代码。

- Jack Lloyd

---

Stepanov在他的《程序设计元素》一书中对此进行了非常易于阅读的演示。 - Paul Nathan

Answer 2

一般的解决方案是使用两个移动速度不同的指针。如果链表中存在循环部分，它们最终会相等。代码大致如下：

 function boolean hasLoop(Node startNode){
   Node slowNode = startNode;
   Node fastNode1 = startNode;
   Node fastNode2 = startNode;

   while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
     if (slowNode == fastNode1 || slowNode == fastNode2) 
        return true;

     slowNode = slowNode.next();
   }
   return false;
 }

以下内容明显是从这里抄袭来的：http://ostermiller.org/find_loop_singly_linked_list.html

- Joel

Answer 3

保留指针值的哈希表。每次访问一个节点时，对其指针进行哈希并存储。如果你发现已经存储了这个节点，那么你就知道你的列表是循环的。

如果你的哈希表是常数级别的，那么这是一个O(n)算法。

- Edward Strange

---

我认为即使哈希表自动扩展，时间复杂度仍然是O(n)。 - Justin K

Answer 4

另一个选项是，由于该列表是双向链接的，您可以遍历该列表并检查下一个指针的前一个是否始终为当前节点或null而不是头部。这里的想法是循环必须要么包含整个列表，要么看起来像这样：

 - -*- \
     \  \
      \---

在 Node * 中，只有 2 个传入链接，其中一个是先前的链接。

类似于：

 bool hasCycle(Node head){
    if( head->next == head ) return true;

    Node current = head -> next;

    while( current != null && current->next != null ) {
         if( current == head || current->next->prev != current )
            return true;

         current = current->next;
    }
    return false; // since I've reached the end there can't be a cycle.
 }

- Joel

---

这个想法不错，但是代码写成这样的话，如果前两个节点不为空，它总是返回true。 - Dave L.

@Dave L.：好发现。不过我认为这样修复了。 - Joel

Answer 5

这里是一种干净的方法来测试一个链表是否有循环（如果它是循环的），基于Floyd算法：

int HasCycle(Node* head)
{
    Node *p1 = head;
    Node *p2 = head;

  while (p1 && p2) { 
        p1 = p1->next;
        p2 = p2->next->next;

        if (p1 == p2)
            return 1;
    }
    return 0;
}

这个想法是使用两个指针，都从head开始，以不同的速度前进。如果它们相遇，那就是我们的线索，说明列表中存在一个循环；否则，该列表没有循环。

- Teodor Ciuraru

Answer 6

这是一个双向链表，每个节点都有“next”和“previous”指针。

双向链表通常使用指向NULL的头部和尾部来实现，以表示它们的结束位置。

[编辑]正如指出的那样，这只检查整个列表是否为循环，而不是其中是否存在循环，但这是原始问题的措辞。如果列表是循环的，则tail->next == head和/或head->prev == tail。如果您没有访问尾部和头部节点，而只有其中一个，则仅检查head->prev！= NULL或tail->next！= NULL即可。

如果这不是一个充分的答案，因为我们只给了一些随机节点[并且正在寻找列表中的任何地方的循环]，那么您所要做的就是取这个随机节点并继续遍历列表，直到达到匹配的节点（在这种情况下它是循环的）或空指针（在这种情况下它不是）。

然而，这本质上与您已经提供的答案相同，但面试官不喜欢。我非常确定，除非有一些神奇的黑客，否则没有办法在提供随机节点的情况下检测链表中的循环，而不使用线性复杂度算法。

[编辑] 我现在已经转换思路，专注于检测列表中的循环，而不是确定链表是否为循环。

如果我们有这样一个情况：

1<->2<->3<->[2]

我唯一能想到的检测循环的方法是跟踪我们迄今为止遍历过的所有元素，并查找沿途的任何匹配项。

当然，这可能很便宜。如果我们被允许修改列表节点，我们可以在每个节点上保留一个简单的遍历标志，我们在执行此操作时设置该标志。如果我们遇到已经设置了此标志的节点，则表示我们已经找到了一个循环。但是，这对并行性的效果不好。

这里提出了一个解决方案[我从另一个答案中窃取的]，称为“弗洛伊德的循环查找算法”。让我们来看一下它（修改后使其更容易阅读）。

function boolean hasLoop(Node startNode)
{
    Node fastNode2 = startNode;
    Node fastNode1 = startNode;
    Node slowNode = startNode;

    while ( slowNode && (fastNode1 = fastNode2.next()) && (fastNode2 = fastNode1.next()) )
    {
        if (slowNode == fastNode1 || slowNode == fastNode2) 
            return true;
        slowNode = slowNode.next();
    }
    return false;
}

这个程序相关的操作基本上是使用3个迭代器而不是1个。我们可以看一个例子：1->2->3->4->5->6->[2]。

首先，我们从[1]开始，用快速迭代器到[2]，另一个在[3]或[1, 2, 3]。当第一个迭代器与两个第二个迭代器中的任意一个匹配时停止。

然后我们继续使用[2, 4, 5]（第一个快速迭代器遍历第二个快速迭代器的下一个节点，第二个快速迭代器在此之后遍历第一个快速迭代器的下一个节点）。然后是[3, 6, 2]，最后是[4, 3, 4]。

太棒了，我们找到了一个匹配，并确定该列表在4次迭代中包含一个循环。

- stinky472

---

我几乎可以确定面试问题实际上是关于检测列表中是否存在循环，而不一定是从第一个元素开始。 - Mike Daniels

@Joel 在问题的重新表述为带有循环的列表而不是检测列表是否为循环列表后，我的思维方式发生了转变。前一种措辞完全让我迷惑了。你能否现在审查我提出的解决方案并给我你的想法？现在我也很好奇。 - stinky472

@stinky472 两种解决方案都有限制条件 -- 第一种解决方案需要一个哈希表才能高效，这将需要O(n)的空间。第二种解决方案不太通用，因为它需要修改节点。 - Joel

@Joel 现在我在我的答案中提问了，但是你可以看一下我在乌龟和兔子案例（使用三个迭代器）中做错了什么吗？ - stinky472

@stinky472，你的快速迭代器和慢速迭代器移动的速度相同。实际跟踪结果如下：[1,2,3]，[2,4,5]，[3,6,2]，[4,3,4] -- 然后你就完成了。 - Joel

Answer 7

你需要的是Floyd循环查找算法。你也可以把寻找循环交点看作一项作业。

- josh

Answer 8

你可以这样处理一个完整的循环链表：通过第一个元素遍历整个链表，直到到达链表末尾或回到第一个元素。

但是，如果你想处理部分循环链表的情况，那么你需要定期移动第一个指针。

- Brian R. Bondy

---

如果列表包含不从第一个元素开始的循环，则您将无法返回到第一个元素。 - Mike Daniels

@Mike：是的，请看第二部分，也许你在我还在写的时候就写了这个。 - Brian R. Bondy

在一维链表中，要么整个列表是一个循环，要么列表不包含循环。 - JohnMcG

@JohnMcG：同意，但我认为这不是发帖者的意图。我认为他们想要检测像A->B->C->D->C->D->C->D->C->D...这样的东西。 - Brian R. Bondy

@Brian R. Bondy：一个一致的双向链表不可能（合理地）包含像那样的循环，因为C不能有两个前置指针，一个指向B，一个指向D。 - caf

Answer 9

开始时，两个指针指向同一个元素。一个指针沿着链表遍历，按照next指针的方向前进。另一个指针则按照previous指针的方向遍历链表。如果两个指针相遇，则说明链表是循环的。如果你发现一个元素的previous或next指针设置为NULL，那么你就知道该链表不是循环的。

- bta

---

这个不起作用。列表中可能有一个循环，这个算法无法找到它。 - Mike Daniels

如果您正在循环中执行此操作，请勿在每次迭代中移动两个指针。如果您这样做，并且列表中的项目数为奇数，则指针可能会在您检查它们是否相遇之前相互穿过。 - Scott Langham

@Mike Daniels- OP试图检测列表是否为循环的，而不是列表中是否存在循环（至少我是这样理解问题的）。 @Scott Langham- 谢谢，我应该在我的答案中澄清这一点。每次迭代只移动一个指针。向相反方向移动两个指针的原因是更快地找到列表的末尾（如果它不是循环的）。 - bta

@Scott，不要试图改进这个。如果我有一个链表A->B->C->D->B，并且我将两个指针都从A开始，那我已经栽了。 - Mike Daniels

在一维链表中，要么整个列表是一个循环，要么列表不包含循环。不存在子列表是循环的情况，也不存在在循环之外的节点。如果是图形结构，则情况会有所不同。 - JohnMcG

@Mike Daniels- 列表A->B->C->D->B不在此问题范围之内，因为这是一个双向链表，在您的示例中元素B将没有明确的“previous”指针。 - bta

Answer 10

假设有人说“这是一个指向列表成员的指针。它是否是循环列表的成员？”那么你可以沿着列表在一个方向上检查所有可达成员，以查找指向他们所给出的指向你指向的节点的指针。如果你决定往下一个方向走，则寻找等于你首先得到的指针的next指针。如果您选择向prev方向前进，则寻找与您首先给出的指针相等的prev指针。如果您在任一方向上到达了NULL指针，则已经找到了末尾，并知道它不是循环的。

你可以通过同时向两个方向走并看看是否会撞到自己来扩展这一点，但它变得更加复杂，而且真的没有节省任何东西。即使您在多核机器上使用2个线程实现此操作，您也将处理共享易失性内存比较，这将影响性能。

或者，如果您可以标记列表中的每个节点，您可以尝试在搜索结束时查找标记以确定是否存在循环。如果您在节点中找到了自己的标记，则知道您之前已经到过那里。如果您在找到其中一个标记之前找到了结束节点，则知道它不是循环的。但是，如果另一个线程同时尝试执行此操作，则此方法将无法正常工作，因为您的标记会混淆。而另一种实现方式如果在测试期间有其他线程正在重新排序列表，则也无法正常工作。

- nategoose