给定一个链表，个解检查链表是决办检测否有循环。下图显示了带有循环的法教链表。
以下是中中执行此操作的不同方法
解决方案1：散列方法：
遍历该列表，并将节点地址始终放在哈希表中。链表在任何时候，循环如果达到NULL，个解则返回false，决办检测如果当前节点的法教下一个指向Hash中先前存储的任何节点，则返回true。中中
#include <bits/stdc++.h> using namespace std; struct Node { int data; struct Node* next; }; void push(struct Node** head_ref,链表 int new_data) { struct Node* new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } bool detectLoop(struct Node* h) { unordered_set<Node*> s; while (h != NULL) { if (s.find(h) != s.end()) return true; s.insert(h); h = h->next; } return false; } int main() { struct Node* head = NULL; push(&head, 20); push(&head, 4); push(&head, 15); push(&head, 10); head->next->next->next->next = head; if (detectLoop(head)) cout << "Loop found"; else cout << "No Loop"; return 0; } 复杂度分析：
时间复杂度：
O（n）。
只需循环一次即可。循环 辅助空间：
O（n）。个解
n是决办检测将值存储在哈希图中所需的空间。 解决方案2：
通过修改链表数据结构，法教无需哈希图即可解决此问题。
方法：此解决方案需要修改基本链表数据结构。 每个节点都有一个访问标志。 遍历链接列表并继续标记访问的节点。 如果您再次看到一个访问过的节点，那么就会有一个循环。该解决方案适用于O（n），但每个节点都需要其他信息。 此解决方案的服务器托管一种变体不需要修改基本数据结构，可以使用哈希来实现，只需将访问的节点的地址存储在哈希中，如果您看到哈希中已经存在的地址，则存在一个循环。 C++：
#include <bits/stdc++.h> using namespace std; struct Node { int data; struct Node* next; int flag; }; void push(struct Node** head_ref, int new_data) { struct Node* new_node = new Node; new_node->data = new_data; new_node->flag = 0; new_node->next = (*head_ref); (*head_ref) = new_node; } bool detectLoop(struct Node* h) { while (h != NULL) { if (h->flag == 1) return true; h->flag = 1; h = h->next; } return false; } int main() { struct Node* head = NULL; push(&head, 20); push(&head, 4); push(&head, 15); push(&head, 10); head->next->next->next->next = head; if (detectLoop(head)) cout << "Loop found"; else cout << "No Loop"; return 0; } 复杂度分析：
时间复杂度：
O（n）。
只需循环一次即可。 辅助空间：
O（1）。
不需要额外的空间。 解决方案3：Floyd的循环查找算法方法：这是最快的方法，下面进行了介绍：
使用两个指针遍历链表。 将一个指针（slow_p）移动一个，将另一个指针（fast_p）移动两个。 如果这些指针在同一节点相遇，则存在循环。如果指针不符合要求，则链接列表没有循环。 Floyd的循环查找算法的实现：
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; }; void push(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } int detectLoop(Node* list) { 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) { return 1; } } return 0; } int main() { Node* head = NULL; push(&head, 20); push(&head, 4); push(&head, 15); push(&head, 10); head->next->next->next->next = head; if (detectLoop(head)) cout << "Loop found"; else cout << "No Loop"; return 0; } 解决方案4：在不修改链接列表数据结构的情况下标记访问的节点
在此方法中，将创建一个临时节点。使遍历的每个节点的下一个指针指向该临时节点。网站模板这样，我们将节点的下一个指针用作标志来指示该节点是否已遍历。检查每个节点以查看下一个节点是否指向临时节点。在循环的第一个节点的情况下，第二次遍历该条件将成立，因此我们发现该循环存在。如果遇到一个指向null的节点，则循环不存在。
下面是上述方法的实现： #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; } void printList(Node* head) { while (head != NULL) { cout << head->key << " "; head = head->next; } cout << endl; } bool detectLoop(Node* head) { Node* temp = new Node; while (head != NULL) { if (head->next == NULL) { return false; } if (head->next == temp) { return true; } Node* nex = head->next; head->next = temp; head = nex; } return false; } int main() { Node* head = newNode(1); head->next = newNode(2); head->next->next = newNode(3); head->next->next->next = newNode(4); head->next->next->next->next = newNode(5); head->next->next->next->next->next = head->next->next; bool found = detectLoop(head); if (found) cout << "Loop Found"; else cout << "No Loop"; return 0; } 复杂度分析：
时间复杂度：
O（n）。
只需循环一次即可。 辅助空间：
O（1）。
不需要空间。 解决方案5：存放长度
在此方法中，将创建两个指针，第一个（始终指向头）和最后一个指针。每次最后一个指针移动时，我们都会计算第一个和最后一个之间的节点数，并检查当前节点数是否大于先前的节点数，如果是，我们通过移动最后一个指针进行操作，否则就意味着我们已经到达循环的服务器租用终点，因此我们相应地返回输出。
#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; } void printList(Node* head) { while (head != NULL) { cout << head->key << " "; head = head->next; } cout << endl; } int distance(Node* first, Node* last) { int counter = 0; Node* curr; curr = first; while (curr != last) { counter += 1; curr = curr->next; } return counter + 1; } bool detectLoop(Node* head) Node* temp = new Node; Node *first, *last; first = head; last = head; int current_length = 0; int prev_length = -1; while (current_length > prev_length && last != NULL) { prev_length = current_length; current_length = distance(first, last); last = last->next; } if (last == NULL) { return false; } else { return true; } } int main() { Node* head = newNode(1); head->next = newNode(2); head->next->next = newNode(3); head->next->next->next = newNode(4); head->next->next->next->next = newNode(5); head->next->next->next->next->next = head->next->next; bool found = detectLoop(head); if (found) cout << "Loop Found"; else cout << "No Loop Found"; return 0; } }