重庆分公司,新征程启航

为企业提供网站建设、域名注册、服务器等服务

C++中检测链表中的循环方法有哪些

这篇文章主要讲解了“C++中检测链表中的循环方法有哪些”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“C++中检测链表中的循环方法有哪些”吧!

五河网站建设公司成都创新互联,五河网站设计制作,有大型网站制作公司丰富经验。已为五河1000+提供企业网站建设服务。企业网站搭建\外贸营销网站建设要多少钱,请找那个售后服务好的五河做网站的公司定做!

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

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 << "Loop found";     else         cout << "No Loop";       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 << "Loop found";     else         cout << "No Loop";       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 << "Loop found";     else         cout << "No Loop";     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->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  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++中检测链表中的循环方法有哪些
标题来源:http://cqcxhl.com/article/giedic.html

其他资讯

在线咨询
服务热线
服务热线:028-86922220
TOP