32

确定链表中是否有循环的最佳（停止）算法是什么？

[编辑] 时间和空间的渐近复杂度分析会很不错，因此可以更好地比较答案。

[编辑] 原始问题不是解决 outdegree > 1 的节点，但有一些讨论。这个问题更像是“在有向图中检测循环的最佳算法”。

4

13 回答 13

51

有两个指针遍历列表；让一个以两倍于另一个的速度迭代，并在每一步比较它们的位置。在我的头顶上，类似：

node* tortoise(begin), * hare(begin);
while(hare = hare->next)
{
    if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
    hare = hare->next;
    if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
    tortoise = tortoise->next;
}

O(n)，这是你能得到的最好的。

于 2008-08-29T09:34:18.277 回答
2

前提条件：跟踪列表大小（在添加或删除节点时更新大小）。

环路检测：

  1. 遍历列表大小时保留一个计数器。

  2. 如果计数器超过列表大小，则可能存在循环。

复杂度：O(n)

注意：计数器和列表大小的比较，以及列表大小的更新操作，必须是线程安全的。

于 2011-05-16T22:18:58.840 回答
1

取 2 个指针 *p 和 *q ，使用两个指针开始遍历链表“LL”：

1）指针p每次都会删除前一个节点并指向下一个节点。

2) 指针 q 每次只会向前走。

条件：

1) 指针 p 指向 null 并且 q 指向某个节点：存在循环

2）两个指针都指向null：没有循环

于 2015-07-24T10:17:57.277 回答
0

使用哈希表来存储已经看到的节点怎么样（您从列表的开头按顺序查看它们）？在实践中，您可以获得接近 O(N) 的结果。

否则，使用排序堆而不是哈希表将实现 O(N log(N))。

于 2008-08-29T09:33:50.697 回答
0

我想知道除了迭代之外是否还有其他方法 - 在您前进时填充一个数组，并检查当前节点是否已经存在于数组中......

于 2008-08-29T09:34:45.017 回答
0

如果循环不指向起点，康拉德鲁道夫的算法将不起作用。以下列表将使其成为无限循环：1->2->3->2。

DrPizza 的算法绝对是要走的路。

于 2008-08-29T09:46:24.677 回答
0

在这种情况下，OysterD 的代码将是最快的解决方案（顶点着色）

那真的会让我大吃一惊。我的解决方案最多通过列表两次（如果最后一个节点链接到倒数第二个矿脉），并且在常见情况下（无循环）只会通过一次。没有散​​列，没有内存分配等。

于 2008-08-29T09:52:44.037 回答
0

在这种情况下，OysterD 的代码将是最快的解决方案（顶点着色）

那真的会让我大吃一惊。我的解决方案最多通过列表两次（如果最后一个节点链接到倒数第二个矿脉），并且在常见情况下（无循环）只会通过一次。没有散​​列，没有内存分配等。

是的。我注意到这个公式并不完美，并改写了它。我仍然相信一个聪明的散列可能会执行得更快——只差一点点。不过，我相信您的算法是最好的解决方案。

只是为了强调我的观点：vertec 着色用于检测现代垃圾收集器的依赖循环，因此它有一个非常真实的用例。他们主要使用位标志来执行着色。

于 2008-08-29T09:58:35.397 回答
0

您将不得不访问每个节点来确定这一点。这可以递归地完成。为了阻止您访问已经访问过的节点，您需要一个标志来表示“已经访问过”。这当然不会给你循环。因此，不要使用位标志，而是使用数字。从 1 开始。检查连接的节点，然后将它们标记为 2 并递归直到网络被覆盖。如果在检查节点时遇到比当前节点少一个以上的节点，那么您就有一个循环。周期长度由差值给出。

于 2008-09-26T15:05:15.297 回答
0

两个指针在链表的头部初始化。一个指针每一步前进一次，另一个指针每一步前进两次。如果较快的指针再次遇到较慢的指针，则列表中存在循环。否则，如果更快的到达列表末尾，则没有循环。

下面的示例代码就是按照这个方案来实现的。较快的指针是 pFast，较慢的指针是 pSlow。

bool HasLoop(ListNode* pHead)
{
    if(pHead == NULL)
        return false;


    ListNode* pSlow = pHead->m_pNext;
    if(pSlow == NULL)
        return false;


    ListNode* pFast = pSlow->m_pNext;
    while(pFast != NULL && pSlow != NULL)
    {
        if(pFast == pSlow)
            return true;


        pSlow = pSlow->m_pNext;


        pFast = pFast->m_pNext;
        if(pFast != NULL)
            pFast = pFast->m_pNext;
    }


    return false;
}

此解决方案可在我的博客上找到。博客中讨论了一个比较多的问题：当列表中有循环/循环时，入口节点是什么？

于 2012-12-28T13:35:51.807 回答
0

“Hack”解决方案（应该在 C/C++ 中工作）：

  • 遍历列表，并将next指针的最后一位设置为 1。
  • 如果找到带有标记指针的元素 - 返回 true 和循环的第一个元素。
  • 在返回之前，将指针重置回来，尽管我相信即使使用标记的指针也可以解除引用。

时间复杂度为 2n。看起来它不使用任何时间变量。

于 2013-10-31T08:02:21.073 回答
0

这是一个使用哈希表（实际上只是一个列表）来保存指针地址的解决方案。

def hash_cycle(node):
    hashl=[]
    while(node):
        if node in hashl:
            return True
        else:
            hashl.append(node)
            node=node.next
    return False
于 2016-07-19T08:16:32.163 回答
0

def has_cycle(head): counter = set()

while head is not None:
    if head in counter:
        return True
    else:
        counter.add(head)
        head = head.next
于 2018-07-16T14:54:41.143 回答