C++中檢測(cè)鏈表中的循環(huán)方法有哪些

這篇文章主要講解了“C++中檢測(cè)鏈表中的循環(huán)方法有哪些”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“C++中檢測(cè)鏈表中的循環(huán)方法有哪些”吧！

給定一個(gè)鏈表，檢查鏈表是否有循環(huán)。下圖顯示了帶有循環(huán)的鏈表。

以下是執(zhí)行此操作的不同方法

解決方案1：散列方法：

遍歷該列表，并將節(jié)點(diǎn)地址始終放在哈希表中。在任何時(shí)候，如果達(dá)到NULL，則返回false，如果當(dāng)前節(jié)點(diǎn)的下一個(gè)指向Hash中先前存儲(chǔ)的任何節(jié)點(diǎn)，則返回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; }

復(fù)雜度分析：

時(shí)間復(fù)雜度： O（n）。
只需循環(huán)一次即可。

輔助空間： O（n）。
n是將值存儲(chǔ)在哈希圖中所需的空間。

解決方案2：通過(guò)修改鏈表數(shù)據(jù)結(jié)構(gòu)，無(wú)需哈希圖即可解決此問(wèn)題。
方法：此解決方案需要修改基本鏈表數(shù)據(jù)結(jié)構(gòu)。

• 每個(gè)節(jié)點(diǎn)都有一個(gè)訪問(wèn)標(biāo)志。

• 遍歷鏈接列表并繼續(xù)標(biāo)記訪問(wèn)的節(jié)點(diǎn)。

• 如果您再次看到一個(gè)訪問(wèn)過(guò)的節(jié)點(diǎn)，那么就會(huì)有一個(gè)循環(huán)。該解決方案適用于O（n），但每個(gè)節(jié)點(diǎn)都需要其他信息。

• 此解決方案的一種變體不需要修改基本數(shù)據(jù)結(jié)構(gòu)，可以使用哈希來(lái)實(shí)現(xiàn)，只需將訪問(wèn)的節(jié)點(diǎn)的地址存儲(chǔ)在哈希中，如果您看到哈希中已經(jīng)存在的地址，則存在一個(gè)循環(huá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; }

復(fù)雜度分析：

時(shí)間復(fù)雜度： O（n）。
只需循環(huán)一次即可。

輔助空間： O（1）。
不需要額外的空間。

解決方案3：Floyd的循環(huán)查找算法
方法：這是最快的方法，下面進(jìn)行了介紹：

• 使用兩個(gè)指針遍歷鏈表。

• 將一個(gè)指針（slow_p）移動(dòng)一個(gè)，將另一個(gè)指針（fast_p）移動(dòng)兩個(gè)。

• 如果這些指針在同一節(jié)點(diǎn)相遇，則存在循環(huán)。如果指針不符合要求，則鏈接列表沒(méi)有循環(huán)。

Floyd的循環(huán)查找算法的實(shí)現(xiàn)：

#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：在不修改鏈接列表數(shù)據(jù)結(jié)構(gòu)的情況下標(biāo)記訪問(wèn)的節(jié)點(diǎn)
在此方法中，將創(chuàng)建一個(gè)臨時(shí)節(jié)點(diǎn)。使遍歷的每個(gè)節(jié)點(diǎn)的下一個(gè)指針指向該臨時(shí)節(jié)點(diǎn)。這樣，我們將節(jié)點(diǎn)的下一個(gè)指針用作標(biāo)志來(lái)指示該節(jié)點(diǎn)是否已遍歷。檢查每個(gè)節(jié)點(diǎn)以查看下一個(gè)節(jié)點(diǎn)是否指向臨時(shí)節(jié)點(diǎn)。在循環(huán)的第一個(gè)節(jié)點(diǎn)的情況下，第二次遍歷該條件將成立，因此我們發(fā)現(xiàn)該循環(huán)存在。如果遇到一個(gè)指向null的節(jié)點(diǎn)，則循環(huán)不存在。
下面是上述方法的實(shí)現(xiàn)：

#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; }

復(fù)雜度分析：

時(shí)間復(fù)雜度： O（n）。
只需循環(huán)一次即可。

輔助空間： O（1）。
不需要空間。

解決方案5：存放長(zhǎng)度

在此方法中，將創(chuàng)建兩個(gè)指針，第一個(gè)（始終指向頭）和最后一個(gè)指針。每次最后一個(gè)指針移動(dòng)時(shí)，我們都會(huì)計(jì)算第一個(gè)和最后一個(gè)之間的節(jié)點(diǎn)數(shù)，并檢查當(dāng)前節(jié)點(diǎn)數(shù)是否大于先前的節(jié)點(diǎn)數(shù)，如果是，我們通過(guò)移動(dòng)最后一個(gè)指針進(jìn)行操作，否則就意味著我們已經(jīng)到達(dá)循環(huán)的終點(diǎn)，因此我們相應(yīng)地返回輸出。

#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; }

}

感謝各位的閱讀，以上就是“C++中檢測(cè)鏈表中的循環(huán)方法有哪些”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)C++中檢測(cè)鏈表中的循環(huán)方法有哪些這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！