在 C++ 中检测并移除链表中的环

2025年3月17日 | 阅读 8 分钟

在本文中，我们将讨论如何在 C++ 中使用不同的方法检测和移除链表中的循环。

创建一个名为 detectAndRemoveLoop() 的函数，该函数验证给定链表是否存在循环。如果存在，它将移除循环并返回 true。如果列表中不存在循环，则返回 false。下图描绘了一个带有循环的链表。下面的列表必须使用 detectAndRemoveLoop() 方法更改为 1->2->3->4->5->NULL。

Detect and Remove Loop in a Linked List in C++

编写一个 C 函数来检测链表中的循环。

在尝试移除循环之前，我们必须首先识别循环。循环可以使用上面讨论的方法找到。我们所要做的就是获取指向循环最后一个节点的指针，以终止循环。考虑上图中值为 5 的节点。一旦我们知道哪个节点是最后一个节点，我们就可以将此链中的下一个节点设置为 NULL 以终止循环。
我们可以快速应用哈希或访问节点方法来获取指向最后一个节点的指针。概念很简单：最后一个节点是其下一个节点已被访问（或哈希）的第一个节点。
弗洛伊德循环检测 技术也可以用于查找和移除循环。弗洛伊德算法中的慢指针和快指针会在循环节点处相遇。此循环节点可用于移除循环。当弗洛伊德技术检测到循环时，有两种不同的方法可以中断循环。

方法 1：（分别检查每个）

已知 弗洛伊德循环检测 过程在快指针和慢指针在同一位置碰撞时结束。此外，我们知道这个公共点是循环节点之一（上图中的 2、3、4 或 5）。将此位置放入指针变量中，例如 ptr2。之后，从链表的头部开始，通过单独检查每个节点来确定每个节点是否可从 ptr2 到达。当链表中的节点可到达时，我们可以获取指向该节点前一个节点的指针，表明该节点代表循环的开始。

输出

Linked List after removing Loop 
50 20 15 4 10

方法 2：（更好的解决方案）

此技术也需要 弗洛伊德循环检测
通过使用弗洛伊德循环检测技术查找循环，获取指向循环节点的指针。
计算循环中有多少个节点。设 k 为计数。
一个指针应固定在头部，另一个指针应固定在距离头部第 k 个节点处。
如果我们将两个指针以相同的速度移动，它们将在循环的起始节点处碰撞。
获取指向循环最后一个节点的指针，并将其下一个节点设置为 NULL。

程序

让我们举一个例子来说明如何在 C++ 中检测和移除链表中的循环。

#include <bits/stdc++.h>
using namespace std;
/* Link list node */
struct Node {
int data;
struct Node* next;
};
/* Function to remove Loop. */
void removeLoop(struct Node*, struct Node*);
/* This Function detects and removes Loop in the 
List

If Loop was there in the List, then it returns 1,
otherwise returns 0 */
int detectAndRemoveLoop(struct Node* list)
{
struct Node *slow_p = list, *fast_p = list;
// Iterate and find if Loop exists or not
while (slow_p && fast_p && fast_p->next) {
slow_p = slow_p->next;
fast_p = fast_p->next->next;
/* If slow_p and fast_p meet at some point, then there is a loop */
if (slow_p == fast_p) {
removeLoop(slow_p, list);
/* Return 1 to indicate that Loop is found */
return 1;
}
}
/* Return 0 to indicate that there is no loop*/
return 0;
}
/* Function to remove Loop.
loop_node --> Pointer to one of the loop nodes
head --> Pointer to the start node of the linked list */
void removeLoop(struct Node* loop_node, struct Node* head)
{
struct Node* ptr1 = loop_node;
struct Node* ptr2 = loop_node;
// Count the number of nodes in the Loop
unsigned int k = 1, i;
while (ptr1->next != ptr2) {
ptr1 = ptr1->next;
k++;
}
// Fix one pointer to head
ptr1 = head;
// And the other pointer to k nodes after head
ptr2 = head;
for (i = 0; i < k; i++)
ptr2 = ptr2->next;
/* Move both pointers at the same pace,
	they will meet at Loop starting node */
while (ptr2 != ptr1) {
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
// Get a pointer to the last node
while (ptr2->next != ptr1)
ptr2 = ptr2->next;
/* Set the next node of the Loop ending node
	to fix the Loop */
ptr2->next = NULL;
}
/* Function to print linked List */
void printList(struct Node* node)
{
// Print the List after loop removal
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
struct Node* newNode(int key)
{
struct Node* temp = new Node();
temp->data = key;
temp->next = NULL;
return temp;
}
// Driver Code
int main()
{
struct Node* head = newNode(35);
head->next = newNode(10);
head->next->next = newNode(12);
head->next->next->next = newNode(54);
head->next->next->next->next = newNode(5);
/* Create a loop for testing */
head->next->next->next->next->next = head->next->next;
detectAndRemoveLoop(head);
cout << "Linked List after removing loop \n";
printList(head);
return 0;
}

输出

复杂度分析

时间复杂度： O(N)，其中 N 是树中的节点数

辅助空间： O(1)

方法 3：（不计算循环中的节点数）

无需计算循环中的节点数。在识别循环之后，如果我们以相同的速度移动快指针和慢指针直到快指针不相遇，它们将在循环的开始处碰撞。

这是如何工作的？

让 弗洛伊德循环检测 算法导致慢指针和快指针碰撞。下图描绘了发现循环时的场景。

我们可以从上图中得出结论。

Distance traveled by fast pointer = 2 * (Distance traveled by slow pointer)
(m + n*x + k) = 2*(m + n*y + k)
Note that before meeting the point shown above, fast was moving at twice the speed.
x -->  Number of complete cyclic rounds made by 
       fast pointer before they meet the first time
y -->  Number of complete cyclic rounds made by 
       slow pointer before they meet the first time

从上面的方程，我们可以得出以下结论

m + k = (x-2y)*n
Which means m+k is a multiple of n. 
Thus we can write m + k = i*n or m = i*n - k.
Hence, the distance moved by the slow pointer: m, is equal to the distance moved by the fast pointer:
i*n - k or (i-1)*n + n - k (cover the loop completely i-1 times and start from n-k).

因此，如果我们将两个指针再次以相同的速度移动，一个指针（我们称之为 slow）将从链表的头节点开始，而另一个指针（我们称之为 fast）将从相遇点开始。当慢指针到达循环的开始处（已移动 m 步）时，快指针也已移动了 m 步，因为它们现在以相同的速度移动。它们将在开始处碰撞，因为快指针从 k 开始，并且 m+k 是 n 的倍数。

程序

// C++ program to detect and remove Loop
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
struct Node* next;
};
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->next = NULL;
return temp;
}
// A utility function to print a linked list
void printList(Node* head)
{
while (head != NULL) {
cout << head->key << " ";
head = head->next;
}
cout << endl;
}
//Function to detect and remove Loop in a linked list that
// may contain Loop
void detectAndRemoveLoop(Node* head)
{
// If the List is empty or has only one node without Loop
if (head == NULL || head->next == NULL)
return;
Node *slow = head, *fast = head;
// Move slow and fast 1 and 2 steps ahead, respectively.
slow = slow->next;
fast = fast->next->next;
// Search for Loop using slow and fast pointers
while (fast && fast->next) {
if (slow == fast)
break;
slow = slow->next;
fast = fast->next->next;
}
/* If loop exists */
if (slow == fast) {
slow = head;
//This check is needed when slow and fast both meet
// at the head of the LL eg: 1->2->3->4->5 and then
// 5->next = 1, i.e the head of the LL
if (slow == fast)
while (fast->next != slow)
fast = fast->next;
else {
while (slow->next != fast->next) {
slow = slow->next;
fast = fast->next;
}
}
/* since fast->next is the looping point */
fast->next = NULL; /* remove loop */
}
}
/* Driver program to test above Function*/
int main()
{
Node* head = newNode(35);
head->next = head;
head->next = newNode(10);
head->next->next = newNode(54);
head->next->next->next = newNode(5);
head->next->next->next->next = newNode(10);
/* Create a loop for testing */
head->next->next->next->next->next = head;
detectAndRemoveLoop(head);
printf("Linked List after removing loop \n");
printList(head);
return 0;
}

输出

复杂度分析

时间复杂度： O(N)，其中 N 是树中的节点数

辅助空间： O(1)

方法 4：哈希（哈希链表节点的地址）

我们可以通过在无序映射中哈希链表节点的地址来检查元素是否已存在于映射中。我们必须将最后一个节点的下一个指针设置为 NULL，因为如果它存在，我们已经通过循环到达了一个已存在的节点。

程序

// C++ program to detect and remove Loop
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
struct Node* next;
};
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->next = NULL;
return temp;
}
// A utility function to print a linked list
void printList(Node* head)
{
while (head != NULL) {
cout << head->key << " ";
head = head->next;
}
cout << endl;
}
//Function to detect and remove the loop
// in a linked list that may contain Loop
void hashAndRemove(Node* head)
{
// hash map to hash addresses of the linked list nodes
unordered_map<Node*, int> node_map;
// pointer to the last node
Node* last = NULL;
while (head != NULL) {
//If node not present in the map, insert it in the map
if (node_map.find(head) == node_map.end()) {
node_map[head]++;
last = head;
head = head->next;
}
//If present, it is a cycle; make the last node's next pointer NULL
else {
last->next = NULL;
break;
}
}
}
/* Driver program to test above Function*/
int main()
{
Node* head = newNode(35);
head->next = head;
head->next = newNode(10);
head->next->next = newNode(54);
head->next->next->next = newNode(5);
head->next->next->next->next = newNode(10);
/* Create a loop for testing */
head->next->next->next->next->next = head->next->next;
// printList(head);
hashAndRemove(head);
printf("Linked List after removing loop \n");
printList(head);
return 0;
}

输出

复杂度分析

时间复杂度： O(N)，其中 N 是树中的节点数。

辅助空间： O(N)，其中 N 是树中的节点数（由于哈希）。

下一主题C++ 与 Go 语言的区别

在 C++ 中检测并移除链表中的环

编写一个 C 函数来检测链表中的循环。

方法 1：（分别检查每个）

方法 2：（更好的解决方案）

方法 3：（不计算循环中的节点数）

方法 4：哈希（哈希链表节点的地址）

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

在 C++ 中检测并移除链表中的环

编写一个 C 函数来检测链表中的循环。

方法 1：（分别检查每个）

方法 2：（更好的解决方案）

方法 3：（不计算循环中的节点数）

方法 4：哈希（哈希链表节点的地址）

相关帖子

C++ 中 deque::assign 和 deque::empty 的区别

C++ 中达到给定 MEX 的最小增量

DOSBox Turbo C++

C++ std::numeric_limits::max() 和 std::numeric_limits::min()

如何在 C++ 中计算一个数的平方

C++ valarray 的 cshift() 函数

C++ 类，用于防止对象复制

C/C++ mbsrtowcs() 函数

C++ 回文数程序

C++ 滚球迷宫

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题