数据结构单链表之检测和删除链表中的循环 | 第十三套
编写一个函数detectAndRemoveLoop() 来检查给定的链表是否包含循环，如果存在循环，则删除循环并返回 true。如果列表不包含循环，则返回 false。下图显示了一个带有循环的链表。detectAndRemoveLoop() 必须将下面的列表更改为 1->2->3->4->5->NULL。
我们还建议阅读以下帖子作为此处讨论的解决方案的先决条件。编写一个 C 函数来检测链表中的循环 在尝试删除循环之前，我们必须检测它。上面帖子中讨论的技术可用于检测循环。要移除循环，我们需要做的就是获取指向循环最后一个节点的指针。例如，上图中值为 5 的节点。一旦我们有了指向最后一个节点的指针，我们就可以将这个节点的下一个节点设置为 NULL，循环就消失了。
我们可以轻松地使用哈希或访问节点技术（在上面提到的帖子中讨论过）来获取指向最后一个节点的指针。想法很简单：下一个已被访问（或散列）的第一个节点是最后一个节点。
我们也可以使用弗洛伊德循环检测算法来检测和删除循环。在弗洛伊德算法中，慢指针和快指针在循环节点相遇。我们可以使用这个循环节点来移除循环。当使用 Floyd 算法进行循环检测时，有以下两种不同的消除循环方法。
方法一（一一查） 我们知道，当快慢指针在一个公共点相遇时，弗洛伊德循环检测算法就终止了。我们也知道这个公共点是循环节点之一（上图中的 2 或 3 或 4 或 5）。将 this 的地址存储在一个指针变量中，比如 ptr2。之后，从链表的头部开始，一一检查节点是否可以从 ptr2 到达。每当我们找到一个可达的节点时，我们就知道这个节点是链表中循环的起始节点，我们可以得到这个节点的前一个节点的指针。
输出：
Linked List after removing loop 50 20 15 4 10 复制代码
方法二（更好的解决方案）
该方法还依赖于 Floyd's Cycle 检测算法。
使用 Floyd 循环检测算法检测循环并获取指向循环节点的指针。
计算循环中的节点数。让计数为k。
将一个指针固定到头部，另一个指向头部的第 k 个节点。
以相同的速度移动两个指针，它们将在循环起始节点相遇。
获取指向循环最后一个节点的指针并将其下一个设为 NULL。
#include <bits/stdc++.h> using namespace std; struct Node { int data; struct Node* next; }; void removeLoop(struct Node*, struct Node*); int detectAndRemoveLoop(struct Node* list) { struct Node *slow_p = list, *fast_p = list; while (slow_p && fast_p && fast_p->next) { slow_p = slow_p->next; fast_p = fast_p->next->next; if (slow_p == fast_p) { removeLoop(slow_p, list); /* Return 1 to indicate that loop is found */ return 1; } } return 0; } void removeLoop(struct Node* loop_node, struct Node* head) { struct Node* ptr1 = loop_node; struct Node* ptr2 = loop_node; unsigned int k = 1, i; while (ptr1->next != ptr2) { ptr1 = ptr1->next; k++; } ptr1 = head; ptr2 = head; for (i = 0; i < k; i++) ptr2 = ptr2->next; while (ptr2 != ptr1) { ptr1 = ptr1->next; ptr2 = ptr2->next; } while (ptr2->next != ptr1) ptr2 = ptr2->next; ptr2->next = NULL; } void printList(struct Node* node) { 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; } int main() { struct Node* head = newNode(50); head->next = newNode(20); head->next->next = newNode(15); head->next->next->next = newNode(4); head->next->next->next->next = newNode(10); head->next->next->next->next->next = head->next->next; detectAndRemoveLoop(head); cout << "Linked List after removing loop \n"; printList(head); return 0; } 复制代码输出：
Linked List after removing loop 50 20 15 4 10
作者：海拥
链接：https://juejin.cn/post/7015421221495898142