测试链表是否有环的最佳算法

StackOverflow https://stackoverflow.com/questions/34249

题

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

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

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

有帮助吗？

解决方案

有两个指针遍历列表；让其中一个以另一个两倍的速度迭代，并在每一步比较它们的位置。我的脑海里浮现出这样的东西：

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)，这是你能得到的最好的结果。

其他提示

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

循环检测：

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

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

复杂：在）

笔记：计数器和列表大小之间的比较以及列表大小的更新操作必须是线程安全的。

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

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

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

状况：

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

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

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

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

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

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

DrPizza 的算法绝对是正确的选择。

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

这真的会让我感到惊讶。我的解决方案最多对列表进行两次遍历（如果最后一个节点链接到倒数第二个矿脉），并且在常见情况下（无循环）将仅进行一次遍历。没有哈希，没有内存分配等。

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

这真的会让我感到惊讶。我的解决方案最多对列表进行两次遍历（如果最后一个节点链接到倒数第二个矿脉），并且在常见情况下（无循环）将仅进行一次遍历。没有哈希，没有内存分配等。

是的。我注意到这个表述并不完美，并重新表述了它。我仍然相信，聪明的散列可能会执行得更快——快一点。我相信你的算法 是 不过，最好的解决方案。

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

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

两个指针在列表的头部初始化。一个指针每一步前进一次，另一个指针每一步前进两次。如果较快的指针再次遇到较慢的指针，则链表中出现循环。否则，如果较快的到达列表末尾，则不会发生循环。

下面的示例代码就是按照这个方案实现的。较快的指针为 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;
}

该解决方案可在 我的博客. 。博客中还讨论了一个更多的问题：当列表中存在循环时，入口节点是什么？

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

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

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

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

def hash_cycle(node):
    hashl=[]
    while(node):
        if node in hashl:
            return True
        else:
            hashl.append(node)
            node=node.next
    return False

def has_cycle(头):计数器=设置（）

while head is not None:
    if head in counter:
        return True
    else:
        counter.add(head)
        head = head.next
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top