首页 / 知识

关于数据结构：测试链表是否具有循环的最佳算法

2023-04-13 14:40:00

Best algorithm to test if a linked list has a cycle

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

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

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

有两个指针遍历列表。使一个迭代速度是另一个迭代速度的两倍，并比较每个步骤的位置。在我的头顶上，像这样：

1
2
3
4
5
6
7
8

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)，尽你所能。

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

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

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

条件：

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

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

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

循环检测：

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

如果计数器超过列表大小，则可能存在一个周期。

复杂度：O(n)

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

def has_cycle(head)：
计数器= set()

1
2
3
4
5
6

while head is not None:
if head in counter:
return True
else:
counter.add(head)
head = head.next

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

1
2
3
4
5
6
7
8
9

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

" Hack"解决方案(应在C / C ++中运行)：

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

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

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

下面的示例代码是根据此解决方案实现的。速度较快的指针为pFast，速度较慢的指针为pSlow。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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;
}

我的博客上提供了该解决方案。博客中讨论了另一个问题：列表中有循环/循环时，入口节点是什么？

您将必须访问每个节点来确定这一点。这可以递归完成。为了阻止您访问已访问的节点，您需要一个标记来表示"已访问"。当然，这不会给您循环。因此，请使用数字代替位标志。从1开始。检查连接的节点，然后将其标记为2，然后递归直到网络被覆盖。如果在检查节点时遇到的节点比当前节点小一个以上，则您有一个循环。周期长度由差值给出。

In this case OysterD's code will be the fastest solution (vertex coloring)

那真的会让我感到惊讶。我的解决方案最多使列表通过两次(如果最后一个节点链接到倒数第二个极点)，而在通常情况下(无循环)将仅通过一次。没有哈希，没有内存分配等。

是。我注意到这种表述并不完美，因此改写了它。我仍然认为，聪明的哈希运算可能会更快-只需一根头发即可。我相信您的算法是最好的解决方案。

只是为了强调我的观点：Vertec着色被现代垃圾收集器用来检测依赖项中的循环，因此有一个非常实际的用例。他们大多使用位标志来执行着色。

In this case OysterD's code will be the fastest solution (vertex coloring)

那真的会让我感到惊讶。我的解决方案最多使列表通过两次(如果最后一个节点链接到倒数第二个极点)，而在通常情况下(无循环)将仅通过一次。没有哈希，没有内存分配等。

如果周期未指向起点，则Konrad Rudolph的算法将无法工作。以下列表将使其变成无限循环：1-> 2-> 3-> 2。

DrPizza的算法绝对是必经之路。

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

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

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