C+丨如何检查链表中的循环?这5个方案,真是太绝了!

通过5个解决方案教你C++中检测链表中的循环,快来看看,是否对你有帮助!

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

以下是执行此操作的不同方法

解决方案1:散列方法

遍历该列表,并将节点地址始终放在哈希表中。在任何时候,如果达到NULL,则返回false,如果当前节点的下一个指向Hash中先前存储的任何节点,则返回true。

#include 

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 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 

else

cout 

return 0;

}

复杂度分析:

时间复杂度:O(n)。

只需循环一次即可。

辅助空间:O(n)。

n是将值存储在哈希图中所需的空间。

解决方案2:通过修改链表数据结构,无需哈希图即可解决此问题。

方法:此解决方案需要修改基本链表数据结构。

每个节点都有一个访问标志。

遍历链接列表并继续标记访问的节点。

如果您再次看到一个访问过的节点,那么就会有一个循环。该解决方案适用于O(n),但每个节点都需要其他信息。

此解决方案的一种变体不需要修改基本数据结构,可以使用哈希来实现,只需将访问的节点的地址存储在哈希中,如果您看到哈希中已经存在的地址,则存在一个循环。

C++:

#include 

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 

else

cout 

return 0;

}

复杂度分析:

时间复杂度:O(n)。

只需循环一次即可。

辅助空间:O(1)。

不需要额外的空间。

解决方案3:Floyd的循环查找算法方法

这是最快的方法,下面进行了介绍。

使用两个指针遍历链表。

将一个指针(slow_p)移动一个,将另一个指针(fast_p)移动两个。

如果这些指针在同一节点相遇,则存在循环。如果指针不符合要求,则链接列表没有循环。

Floyd的循环查找算法的实现:

#include 

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 

else

cout 

return 0;

}

解决方案4:在不修改链接列表数据结构的情况下标记访问的节点

在此方法中,将创建一个临时节点。使遍历的每个节点的下一个指针指向该临时节点。这样,我们将节点的下一个指针用作标志来指示该节点是否已遍历。检查每个节点以查看下一个节点是否指向临时节点。在循环的第一个节点的情况下,第二次遍历该条件将成立,因此我们发现该循环存在。如果遇到一个指向null的节点,则循环不存在。

下面是上述方法的实现:

#include 

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 = head->next;

}

cout 

}

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 

else

cout 

return 0;

}

复杂度分析:

时间复杂度:O(n)。

只需循环一次即可。

辅助空间:O(1)。

不需要空间。

解决方案5:存放长度

在此方法中,将创建两个指针,第一个(始终指向头)和最后一个指针。每次最后一个指针移动时,我们都会计算第一个和最后一个之间的节点数,并检查当前节点数是否大于先前的节点数,如果是,我们通过移动最后一个指针进行操作,否则就意味着我们已经到达循环的终点,因此我们相应地返回输出。

#include 

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 = head->next;

}

cout 

}

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 

else

cout 

return 0;

}

感谢阅读,希望能帮助到大家,有什么问题欢迎评论区留言。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20201227A09MUF00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券