通過5個解決方案教你C++中檢測鏈表中的回圈，快來看看，是否對你有幫助！
給定一個鏈表，檢查鏈表是否有回圈，下圖顯示了帶有回圈的鏈表，
?
以下是執行此操作的不同方法
解決方案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;
}
感謝閱讀，希望能幫助到大家，有什么問題歡迎評論區留言，
如果你想更好的提升你的編程能力，學好C語言C++編程！彎道超車，快人一步！
【C語言C++學習企鵝圈子】，分享（原始碼、專案實戰視頻、專案筆記，基礎入門教程）
歡迎轉行和學習編程的伙伴，利用更多的資料學習成長比自己琢磨更快哦！
編程學習書籍：
編程學習視頻：
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/241189.html
標籤：C++
下一篇：指標如何在3天內突破，他做到了！