給定一個連結串列，檢查連結串列是否有迴圈。下圖顯示了帶有迴圈的連結串列。

以下是執行此操作的不同方法

解決方案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：存放長度

在此方法中，將建立兩個指標，第一個（始終指向頭）和最後一個指標。每次最後一個指標移動時，我們都會計算第一個和最後一個之間的節點數，並檢查當前節點數是否大於先前的節點數，如果是，我們透過移動最後一個指標進行操作，否則就意味著我們已經到達迴圈的終點，因此我們相應地返回輸出。