如何仅使用两个内存位置确定链表是否有循环

Question

有没有算法可以只使用两个变量来遍历链表并查找它是否与自身形成循环。假设您有一个由对象组成的链表，对象类型不重要。我有一个指向链表头部的指针存在一个变量中，我只能使用另一个变量来遍历整个列表。

我的计划是比较指针值以查看是否有相同的指针。该链表的大小是有限的，但可能非常大。我可以将两个变量都设置为头部，并使用另一个变量遍历列表，始终检查它是否等于另一个变量，但如果我碰到循环，我将无法跳出它。我认为这与遍历列表和比较指针值的速率不同有关。有什么想法吗？

- jeffD

---

谢谢，Turtle和Rabbit确实提供了一个很好的解决方案。从概念上讲，如果列表回到自身，我也喜欢Rabbit绕着Turtle循环的想法。顺便说一下，这个列表不应该是一个循环链表，如果它循环，它可能会指向中间的某个地方。 - jeffD

Answer 1

我建议使用 Floyd's Cycle-Finding Algorithm，又称为The Tortoise and the Hare Algorithm。它的时间复杂度为O(n)，我认为它符合您的要求。

示例代码：

function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

更多信息请参见维基百科：弗洛伊德循环查找算法。

- Baishampayan Ghose

---

是的，你可以轻松修改上面的代码，将fastNode1设置为slowNode.next().next() :) - Baishampayan Ghose

如果我们将“快节点”每次推进三个节点，而不是两个节点，会发生什么？ 我们不能检测到“快节点”已经越过了“慢节点”吗？ 显然，用于检测这一点的相等性检查（目前正在使用的）不一定适用于前进三个节点。 你认为呢？ 这样（一次跳过更多步骤）不会是一种更好的算法吗？ - Lazer

@Lazer - 对于小循环，指针都这样包裹存在风险。 - Flexo

@Lazer：“我们不能检测到fastNode已经越过了slowNode吗？”- 可以的。 “这样（一次跳多个步骤）不会是更好的算法吗？”- 不一定。考虑两种极端情况。链表A是一个有1000000个节点的大循环。链表B有一个非循环的包含1000000个节点的链，最终到达一个只有三个节点的小循环。加速兔子将让您更快地检测到A中的循环（兔子比乌龟更早地完成一圈），但代价是使您在检测B中的循环时变慢（等待乌龟甚至到达循环的时间更长，而兔子则疯狂地在圆圈里奔跑）。这是一个权衡。 - Mark Amery

抱歉挖坟了。但是，如果我们想找到循环实际开始的地方，除了跟踪我们已经看到的所有节点之外，是否有更好的解决方案？ - Kevin

Answer 2

你可以使用龟兔赛跑算法。

维基百科也有解释，他们称之为"弗洛伊德的循环检测算法"或"乌龟和兔子"。

- martinus

---

我已经向[e-mail]发送了一个错误报告。 - martinus

维基百科终于解决了我多年来对这个算法的私人疑惑。感谢您发布此链接。 - user3458

Answer 3

当然可以。一种解决方案是使用两个指针遍历列表，其中一个指针的移动速度是另一个的两倍。

从列表中的任何位置开始，将“慢”指针和“快”指针指向同一个位置。运行遍历循环。如果“快”指针在任何时候与慢指针重合，则表示您有一个循环链表。

int *head = list.GetHead();
if (head != null) {
    int *fastPtr = head;
    int *slowPtr = head;

    bool isCircular = true;

    do 
    {
        if (fastPtr->Next == null || fastPtr->Next->Next == null) //List end found
        {
            isCircular = false;
            break;
        }

        fastPtr = fastPtr->Next->Next;
        slowPtr = slowPtr->Next;
    } while (fastPtr != slowPtr);

    //Do whatever you want with the 'isCircular' flag here
}

- Frederick

---

如果fastPtr恰好在循环顶部的列表中的最后一个元素上，那么这个指针错误不会导致失败吗？ - Lawrence Dol

如果列表为空或只有一个元素，那么在fastPtr的初始赋值中呢？ - Lawrence Dol

当列表没有循环且长度为奇数时，此方法将无效，next->next 会导致空指针异常（或类似的错误）。 - martinus

Answer 4

我试图自己解决这个问题，并找到了另一个（效率较低但仍然是最优的）解决方案。

这个想法基于在线性时间内反转单链表。可以通过在迭代列表时每步进行两次交换来实现。如果q是上一个元素（最初为null），p是当前元素，则swap(q，p->next) swap(p，q)将反转链接并同时推进两个指针。可以使用XOR进行交换，以避免使用第三个内存位置。

如果列表具有循环，则在迭代过程中会到达一个指针已经更改的节点。你不知道那是哪个节点，但是通过继续迭代，对一些元素进行两次交换，最终到达列表头部。

通过两次反转列表，结果看起来与原始列表相同，并且根据是否到达了原始列表的头部，可以确定它是否具有循环。

- user101596

---

由于这需要修改列表，我认为这是一个更糟糕的解决方案。两个可能会出现问题的例子：如果列表可能驻留在常量内存中（例如static const结构或内存映射只读文件），或者如果列表被多个线程使用（只要访问是只读的，就不需要锁定；如果加锁，它将变得非常缓慢和/或阻塞其他线程）。 - R.. GitHub STOP HELPING ICE

Answer 5

int isListCircular(ListNode* head){
    if(head==NULL)
        return 0;
    ListNode *fast=head, *slow=head;
    while(fast && fast->next){
        if(fast->next->next==slow)
            return 1;
        fast=fast->next->next;
        slow=slow->next;
    }
    return 0;
}

- rajya vardhan

Answer 6

boolean findCircular(Node *head)
{
    Node *slower, * faster;
    slower = head;
    faster = head->next;
    while(true) {
        if ( !faster || !faster->next)
            return false;
        else if (faster == slower || faster->next == slower)
            return true;
        else
            faster = faster->next->next;
    }
}

- user5297378

---

不建议仅提供代码答案，尽量简要地解释你所做的事情。 - Unome

Answer 7

将这个问题推进到下一步将是识别循环（即不仅存在循环，而且在列表中确切的位置）。可以使用乌龟和兔子算法来解决此问题，但是我们需要始终跟踪列表的头部。该算法的示例可以在这里找到。

- ND_27