五個解決辦法教你C++中檢測鏈表中的循環(huán)
給定一個鏈表，檢查鏈表是否有循環(huán)。下圖顯示了帶有循環(huán)的鏈表。
以下是執(zhí)行此操作的不同方法
解決方案1：散列方法：
遍歷該列表，并將節(jié)點(diǎn)地址始終放在哈希表中。在任何時候，如果達(dá)到NULL，則返回false，如果當(dāng)前節(jié)點(diǎn)的下一個指向Hash中先前存儲的任何節(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ù)雜度分析：
時間復(fù)雜度： O（n）。
只需循環(huán)一次即可。
輔助空間： O（n）。
n是將值存儲在哈希圖中所需的空間。
解決方案2：通過修改鏈表數(shù)據(jù)結(jié)構(gòu)，無需哈希圖即可解決此問題。
方法：此解決方案需要修改基本鏈表數(shù)據(jù)結(jié)構(gòu)。
- 每個節(jié)點(diǎn)都有一個訪問標(biāo)志。
- 遍歷鏈接列表并繼續(xù)標(biāo)記訪問的節(jié)點(diǎn)。
- 如果您再次看到一個訪問過的節(jié)點(diǎn)，那么就會有一個循環(huán)。該解決方案適用于O（n），但每個節(jié)點(diǎn)都需要其他信息。
- 此解決方案的一種變體不需要修改基本數(shù)據(jù)結(jié)構(gòu)，可以使用哈希來實(shí)現(xiàn)，只需將訪問的節(jié)點(diǎn)的地址存儲在哈希中，如果您看到哈希中已經(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;
- }
復(fù)雜度分析：
時間復(fù)雜度： O（n）。
只需循環(huán)一次即可。
輔助空間： O（1）。
不需要額外的空間。
解決方案3：Floyd的循環(huán)查找算法
方法：這是最快的方法，下面進(jìn)行了介紹：
- 使用兩個指針遍歷鏈表。
- 將一個指針（slow_p）移動一個，將另一個指針（fast_p）移動兩個。
- 如果這些指針在同一節(jié)點(diǎn)相遇，則存在循環(huán)。如果指針不符合要求，則鏈接列表沒有循環(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)記訪問的節(jié)點(diǎn)
在此方法中，將創(chuàng)建一個臨時節(jié)點(diǎn)。使遍歷的每個節(jié)點(diǎn)的下一個指針指向該臨時節(jié)點(diǎn)。這樣，我們將節(jié)點(diǎn)的下一個指針用作標(biāo)志來指示該節(jié)點(diǎn)是否已遍歷。檢查每個節(jié)點(diǎn)以查看下一個節(jié)點(diǎn)是否指向臨時節(jié)點(diǎn)。在循環(huán)的第一個節(jié)點(diǎn)的情況下，第二次遍歷該條件將成立，因此我們發(fā)現(xiàn)該循環(huán)存在。如果遇到一個指向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ù)雜度分析：
時間復(fù)雜度： O（n）。
只需循環(huán)一次即可。
輔助空間： O（1）。
不需要空間。
解決方案5：存放長度
在此方法中，將創(chuàng)建兩個指針，第一個（始終指向頭）和最后一個指針。每次最后一個指針移動時，我們都會計算第一個和最后一個之間的節(jié)點(diǎn)數(shù)，并檢查當(dāng)前節(jié)點(diǎn)數(shù)是否大于先前的節(jié)點(diǎn)數(shù)，如果是，我們通過移動最后一個指針進(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;
- }
}
