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

五河網(wǎng)站建設公司成都創(chuàng)新互聯(lián),五河網(wǎng)站設計制作，有大型網(wǎng)站制作公司豐富經(jīng)驗。已為五河1000+提供企業(yè)網(wǎng)站建設服務。企業(yè)網(wǎng)站搭建\外貿(mào)營銷網(wǎng)站建設要多少錢，請找那個售后服務好的五河做網(wǎng)站的公司定做！

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

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

解決方案1：散列方法：

遍歷該列表，并將節(jié)點地址始終放在哈希表中。在任何時候，如果達到NULL，則返回false，如果當前節(jié)點的下一個指向Hash中先前存儲的任何節(jié)點，則返回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）。
只需循環(huán)一次即可。

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

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

• 每個節(jié)點都有一個訪問標志。

• 遍歷鏈接列表并繼續(xù)標記訪問的節(jié)點。

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

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

復雜度分析：

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

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

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

• 使用兩個指針遍歷鏈表。

• 將一個指針（slow_p）移動一個，將另一個指針（fast_p）移動兩個。

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

Floyd的循環(huán)查找算法的實現(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)的情況下標記訪問的節(jié)點
在此方法中，將創(chuàng)建一個臨時節(jié)點。使遍歷的每個節(jié)點的下一個指針指向該臨時節(jié)點。這樣，我們將節(jié)點的下一個指針用作標志來指示該節(jié)點是否已遍歷。檢查每個節(jié)點以查看下一個節(jié)點是否指向臨時節(jié)點。在循環(huán)的第一個節(jié)點的情況下，第二次遍歷該條件將成立，因此我們發(fā)現(xiàn)該循環(huán)存在。如果遇到一個指向null的節(jié)點，則循環(huán)不存在。
下面是上述方法的實現(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; }

復雜度分析：

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

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

解決方案5：存放長度

在此方法中，將創(chuàng)建兩個指針，第一個（始終指向頭）和最后一個指針。每次最后一個指針移動時，我們都會計算第一個和最后一個之間的節(jié)點數(shù)，并檢查當前節(jié)點數(shù)是否大于先前的節(jié)點數(shù)，如果是，我們通過移動最后一個指針進行操作，否則就意味著我們已經(jīng)到達循環(huá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; } 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++中檢測鏈表中的循環(huán)方法有哪些”的內(nèi)容了，經(jīng)過本文的學習后，相信大家對C++中檢測鏈表中的循環(huán)方法有哪些這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關知識點的文章，歡迎關注！

網(wǎng)站名稱：C++中檢測鏈表中的循環(huán)方法有哪些
網(wǎng)頁網(wǎng)址：http://chinadenli.net/article2/giedic.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站制作、微信公眾號、企業(yè)網(wǎng)站制作、標簽優(yōu)化、域名注冊、定制網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)