五个解决办法教你 C++ 中检测链表中的循环

给定一个链表,检查链表是否有循环。下图显示了带有循环的链表。

五个解决办法教你 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; 

}
}