最佳算法来测试链表是否有循环。

Question

什么是检测链表中是否存在循环的最佳（停机）算法？

[编辑] 分析时间和空间的渐进复杂度会更好，这样答案可以更好地进行比较。

[编辑] 最初的问题没有涉及出度> 1的节点，但有一些讨论。 那个问题更多的是“检测有向图中循环的最佳算法”。

- cdleary

---

https://dev59.com/TnE85IYBdhLWcg3wr1ge - Pramod

可能是如何检测链表中的循环？的重复问题。 - roottraveller

Answer 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)是最好的情况，不能再优化了。

- DrPizza

---

哎呀，实际上你有一个错误。while循环应该是while (hare && hare = hare->next)，否则你可能会在迭代到末尾时继续循环。 - 1800 INFORMATION

你不需要while(hare && hare = hare->next)。唯一保护你的情况是列表为空（根节点为空）。否则，定义的while循环会在hare->next返回null时立即终止。 - Herms

循环体内设置了 hare->next 给 hare，因此此时 hare 有可能是空值。 - Wedge

顺便提一下，“off the top of your head”可能会让某些人误认为你是发明了这个算法，误导人们称其为“DrPizza的算法”！我们应该表扬功劳所在。事实上，这个算法早在1967年就被Floyd发表了：http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare。 - Dimitris Andreou

我的意思是“脑海中想出来的”，指的是“直接在文本框中编写，而不参考编译器或其他任何东西”。然而，你错了；弗洛伊德算法可以找到循环。这里的问题只是确定是否存在循环。两种算法背后的原理是相同的，但后者要简单得多。 - DrPizza

Answer 2

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

循环检测：

1. 在遍历列表时保持计数器。

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

复杂度：O(n)

注意：必须使计数器与列表大小的比较以及列表大小的更新操作具有线程安全性。

- kbsant

Answer 3

拿两个指针 *p 和 *q，使用两个指针开始遍历链表 "LL"：

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

2）指针 q 每次只朝着正方向前进。

条件：

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

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

- mac jc

Answer 4

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

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

- FlyingAura

Answer 5

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

下面的示例代码是根据此解决方案实现的。快指针为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;
}

这个解决方案可以在我的博客上找到。博客中还讨论了一个更棘手的问题：当链表中存在循环/环时，入口节点是什么？

- Harry He

Answer 6

“黑客”解决方案（适用于C/C++）：

• 遍历列表，将next指针的最后一位设置为1。
• 如果发现带有标记指针的元素，则返回true和循环的第一个元素。
• 在返回之前，将指针重置回去，尽管我认为即使使用带标记的指针也可以进行取消引用。

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

- Ayrat

Answer 7

您需要访问每个节点来确定这一点。这可以通过递归完成。为了防止您访问已经访问过的节点，您需要一个标志来表示“已经访问过”。当然，这并不能给您循环。因此，不要使用位标志，而是使用数字。从1开始。检查连接的节点，然后将其标记为2并递归，直到覆盖整个网络。如果在检查节点时遇到一个比当前节点少一个以上的节点，则说明存在一个循环。差异给出了循环长度。

- Jonathan Swift

Answer 8

使用哈希表来存储已经遍历过的节点（你按照列表开始的顺序查看它们）怎么样？实际上，你可以接近O(N)的效果。

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

- OysterD

---

哈希表解决方案的空间复杂度为O(n)。 - jfm3

Answer 9

我想知道是否有其他方法，而不仅仅是迭代地进行 - 在向前移动时填充数组，并检查当前节点是否已经存在于数组中...

- wolfie

Answer 10

Konrad Rudolph的算法如果循环不指向开头，就无法工作。以下列表将使其成为无限循环：1-> 2-> 3-> 2。

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

- Liedman