检测并移除链表中的循环

引言

链表是计算机科学和编程中用于多种目的的基本数据结构。虽然它们提供了更大的动态内存分配灵活性，但如果错误地包含通常称为循环依赖的循环，它们也可能带来困难。为了保护数据完整性并避免可能导致程序崩溃或内存泄漏的无限循环，必须识别和消除链表中的循环。本文将探讨链表中循环检测和消除的技术和算法。

链表基础知识

在链表中，一种线性数据结构，称为节点的元素与其他节点链接。数据和指向链中下一个节点的链接构成每个节点的两个组成部分。最后一个节点通常指向 NULL 以表示列表的结束。链表可以采取多种形式，例如单向链表、双向链表和循环链表。当一个节点或一组节点链接到一个在列表中已被遍历过的节点时，就会出现链表中的循环。

检测循环

在尝试移除循环之前，识别链表中的循环至关重要。Floyd 的龟兔算法和哈希是最常用于完成此任务的算法。

1. Floyd 的龟兔算法

• 该过程使用两个指针——一个慢速指针（乌龟）和一个快速指针（野兔）。
• 野兔每走一步，乌龟就走两步。
• 如果不存在循环，野兔将到达列表的末尾，因此我们可以得出这个结论。
• 如果存在循环，野兔最终会追上乌龟。
• 当它们相遇时，我们可以推断存在一个循环，并计算其大小和位置。

2. 哈希

• 此方法将已访问节点的引用保存在哈希表中。
• 在遍历链表时，我们检查哈希表以查看当前节点的引用是否已存在。
• 如果是，我们发现了一个循环；如果不是，我们将引用添加到哈希表并继续。
• 虽然此方法需要更多的 RAM 来存储哈希表，但它可以有效地检测循环。

移除循环

下一步是在保持链表完整性的同时移除循环。有多种方法可以实现这一点

1. 使用 Floyd 算法

• 使用 Floyd 的技术，我们可以识别循环并计算其长度。
• 接下来，我们在列表的顶部初始化两个指针，一个在头部本身，另一个在 '循环长度' 节点之后。
• 一次移动一个节点，我们将两个指针拉到一起。循环的开始将是相遇点。
• 我们切断从循环开始节点之前节点的链接，以打破循环。

2. 哈希

• 当使用哈希查找循环时，我们可以同时跟踪循环开始的节点。
• 一旦识别出循环，我们就更新节点的 'next' 指针以删除导致循环的引用。

Python 实现

下面提供了使用 Floyd 的龟兔算法和哈希查找和移除单向链表中循环的 Python 代码。

输出

Loop detected.
Loop removed.
1 -> 2 -> 3 -> 4 -> 5 -> None

结论

为了保护数据完整性并避免编程问题，程序员必须熟悉链表中循环的检测和移除。可以使用 Floyd 的龟兔算法和哈希等算法高效地检测循环，并且可以使用多种技术安全地移除它们。