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

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

专注于为中小企业提供网站建设、网站制作服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业宁德免费做网站提供优质的服务。我们立足成都，凝聚了一批互联网行业人才，有力地推动了千余家企业的稳健成长，帮助中小企业通过网站建设实现规模扩充和转变。

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

解决方案1：散列方法：

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

 
 
 
    
  
  
  
  1. #include  
    2. 
  
  
  
  2. using namespace std; 
    3. 
  
  
  
  3. struct Node { 
    4. 
  
  
  
  4.     int data; 
    5. 
  
  
  
  5.     struct Node* next; 
    6. 
  
  
  
  6. }; 
    7. 
  
  
  
  7.   
    8. 
  
  
  
  8. void push(struct Node** head_ref, int new_data) 
    9. 
  
  
  
  9. { 
    10. 
  
  
  
  10.     struct Node* new_node = new Node; 
    11. 
  
  
  
  11.     new_node->data = new_data; 
    12. 
  
  
  
  12.     new_node->next = (*head_ref); 
    13. 
  
  
  
  13.     (*head_ref) = new_node; 
    14. 
  
  
  
  14. } 
    15. 
  
  
  
  15. bool detectLoop(struct Node* h) 
    16. 
  
  
  
  16. { 
    17. 
  
  
  
  17.     unordered_set s; 
    18. 
  
  
  
  18.     while (h != NULL) { 
    19. 
  
  
  
  19.         if (s.find(h) != s.end()) 
    20. 
  
  
  
  20.             return true; 
    21. 
  
  
  
  21.         s.insert(h); 
    22. 
  
  
  
  22.   
    23. 
  
  
  
  23.         h = h->next; 
    24. 
  
  
  
  24.     } 
    25. 
  
  
  
  25.   
    26. 
  
  
  
  26.     return false; 
    27. 
  
  
  
  27. } 
    28. 
  
  
  
  28. int main() 
    29. 
  
  
  
  29. { 
    30. 
  
  
  
  30.     struct Node* head = NULL; 
    31. 
  
  
  
  31.   
    32. 
  
  
  
  32.     push(&head, 20); 
    33. 
  
  
  
  33.     push(&head, 4); 
    34. 
  
  
  
  34.     push(&head, 15); 
    35. 
  
  
  
  35.     push(&head, 10); 
    36. 
  
  
  
  36.     head->next->next->next->next = head; 
    37. 
  
  
  
  37.   
    38. 
  
  
  
  38.     if (detectLoop(head)) 
    39. 
  
  
  
  39.         cout << "Loop found"; 
    40. 
  
  
  
  40.     else 
    41. 
  
  
  
  41.         cout << "No Loop"; 
    42. 
  
  
  
  42.   
    43. 
  
  
  
  43.     return 0; 
    44. 
  
  
  
  44. } 
    45.

复杂度分析：

时间复杂度： O（n）。
只需循环一次即可。

辅助空间： O（n）。
n是将值存储在哈希图中所需的空间。

解决方案2：通过修改链表数据结构，无需哈希图即可解决此问题。
方法：此解决方案需要修改基本链表数据结构。

  • 每个节点都有一个访问标志。
  • 遍历链接列表并继续标记访问的节点。
  • 如果您再次看到一个访问过的节点，那么就会有一个循环。该解决方案适用于O（n），但每个节点都需要其他信息。
  • 此解决方案的一种变体不需要修改基本数据结构，可以使用哈希来实现，只需将访问的节点的地址存储在哈希中，如果您看到哈希中已经存在的地址，则存在一个循环。

C++：

 
 
 
    
  
  
  
  1. #include  
    2. 
  
  
  
  2. using namespace std; 
    3. 
  
  
  
  3. struct Node { 
    4. 
  
  
  
  4.     int data; 
    5. 
  
  
  
  5.     struct Node* next; 
    6. 
  
  
  
  6.     int flag; 
    7. 
  
  
  
  7. }; 
    8. 
  
  
  
  8.   
    9. 
  
  
  
  9. void push(struct Node** head_ref, int new_data) 
    10. 
  
  
  
  10. { 
    11. 
  
  
  
  11.     struct Node* new_node = new Node; 
    12. 
  
  
  
  12.     new_node->data = new_data; 
    13. 
  
  
  
  13.   
    14. 
  
  
  
  14.     new_node->flag = 0; 
    15. 
  
  
  
  15.     new_node->next = (*head_ref); 
    16. 
  
  
  
  16.     (*head_ref) = new_node; 
    17. 
  
  
  
  17. } 
    18. 
  
  
  
  18. bool detectLoop(struct Node* h) 
    19. 
  
  
  
  19. { 
    20. 
  
  
  
  20.     while (h != NULL) { 
    21. 
  
  
  
  21.         if (h->flag == 1) 
    22. 
  
  
  
  22.             return true; 
    23. 
  
  
  
  23.         h->flag = 1; 
    24. 
  
  
  
  24.   
    25. 
  
  
  
  25.         h = h->next; 
    26. 
  
  
  
  26.     } 
    27. 
  
  
  
  27.   
    28. 
  
  
  
  28.     return false; 
    29. 
  
  
  
  29. } 
    30. 
  
  
  
  30. int main() 
    31. 
  
  
  
  31. { 
    32. 
  
  
  
  32.     struct Node* head = NULL; 
    33. 
  
  
  
  33.   
    34. 
  
  
  
  34.     push(&head, 20); 
    35. 
  
  
  
  35.     push(&head, 4); 
    36. 
  
  
  
  36.     push(&head, 15); 
    37. 
  
  
  
  37.     push(&head, 10); 
    38. 
  
  
  
  38.     head->next->next->next->next = head; 
    39. 
  
  
  
  39.   
    40. 
  
  
  
  40.     if (detectLoop(head)) 
    41. 
  
  
  
  41.         cout << "Loop found"; 
    42. 
  
  
  
  42.     else 
    43. 
  
  
  
  43.         cout << "No Loop"; 
    44. 
  
  
  
  44.   
    45. 
  
  
  
  45.     return 0; 
    46. 
  
  
  
  46. } 
    47.

复杂度分析：

时间复杂度： O（n）。
只需循环一次即可。

辅助空间： O（1）。
不需要额外的空间。

解决方案3：Floyd的循环查找算法
方法：这是最快的方法，下面进行了介绍：

  • 使用两个指针遍历链表。
  • 将一个指针（slow_p）移动一个，将另一个指针（fast_p）移动两个。
  • 如果这些指针在同一节点相遇，则存在循环。如果指针不符合要求，则链接列表没有循环。

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

 
 
 
    
  
  
  
  1. #include  
    2. 
  
  
  
  2. using namespace std; 
    3. 
  
  
  
  3. class Node { 
    4. 
  
  
  
  4. public: 
    5. 
  
  
  
  5.     int data; 
    6. 
  
  
  
  6.     Node* next; 
    7. 
  
  
  
  7. }; 
    8. 
  
  
  
  8.   
    9. 
  
  
  
  9. void push(Node** head_ref, int new_data) 
    10. 
  
  
  
  10. { 
    11. 
  
  
  
  11.     Node* new_node = new Node(); 
    12. 
  
  
  
  12.     new_node->data = new_data; 
    13. 
  
  
  
  13.     new_node->next = (*head_ref); 
    14. 
  
  
  
  14.     (*head_ref) = new_node; 
    15. 
  
  
  
  15. } 
    16. 
  
  
  
  16.   
    17. 
  
  
  
  17. int detectLoop(Node* list) 
    18. 
  
  
  
  18. { 
    19. 
  
  
  
  19.     Node *slow_p = list, *fast_p = list; 
    20. 
  
  
  
  20.   
    21. 
  
  
  
  21.     while (slow_p && fast_p && fast_p->next) { 
    22. 
  
  
  
  22.         slow_p = slow_p->next; 
    23. 
  
  
  
  23.         fast_p = fast_p->next->next; 
    24. 
  
  
  
  24.         if (slow_p == fast_p) { 
    25. 
  
  
  
  25.             return 1; 
    26. 
  
  
  
  26.         } 
    27. 
  
  
  
  27.     } 
    28. 
  
  
  
  28.     return 0; 
    29. 
  
  
  
  29. } 
    30. 
  
  
  
  30. int main() 
    31. 
  
  
  
  31. { 
    32. 
  
  
  
  32.     Node* head = NULL; 
    33. 
  
  
  
  33.   
    34. 
  
  
  
  34.     push(&head, 20); 
    35. 
  
  
  
  35.     push(&head, 4); 
    36. 
  
  
  
  36.     push(&head, 15); 
    37. 
  
  
  
  37.     push(&head, 10); 
    38. 
  
  
  
  38.     head->next->next->next->next = head; 
    39. 
  
  
  
  39.     if (detectLoop(head)) 
    40. 
  
  
  
  40.         cout << "Loop found"; 
    41. 
  
  
  
  41.     else 
    42. 
  
  
  
  42.         cout << "No Loop"; 
    43. 
  
  
  
  43.     return 0; 
    44. 
  
  
  
  44. } 
    45.

解决方案4：在不修改链接列表数据结构的情况下标记访问的节点
在此方法中，将创建一个临时节点。使遍历的每个节点的下一个指针指向该临时节点。这样，我们将节点的下一个指针用作标志来指示该节点是否已遍历。检查每个节点以查看下一个节点是否指向临时节点。在循环的第一个节点的情况下，第二次遍历该条件将成立，因此我们发现该循环存在。如果遇到一个指向null的节点，则循环不存在。
下面是上述方法的实现：

 
 
 
    
  
  
  
  1. #include  
    2. 
  
  
  
  2. using namespace std; 
    3. 
  
  
  
  3.   
    4. 
  
  
  
  4. struct Node { 
    5. 
  
  
  
  5.     int key; 
    6. 
  
  
  
  6.     struct Node* next; 
    7. 
  
  
  
  7. }; 
    8. 
  
  
  
  8.   
    9. 
  
  
  
  9. Node* newNode(int key) 
    10. 
  
  
  
  10. { 
    11. 
  
  
  
  11.     Node* temp = new Node; 
    12. 
  
  
  
  12.     temp->key = key; 
    13. 
  
  
  
  13.     temp->next = NULL; 
    14. 
  
  
  
  14.     return temp; 
    15. 
  
  
  
  15. } 
    16. 
  
  
  
  16. void printList(Node* head) 
    17. 
  
  
  
  17. { 
    18. 
  
  
  
  18.     while (head != NULL) { 
    19. 
  
  
  
  19.         cout << head->key << " "; 
    20. 
  
  
  
  20.         head = head->next; 
    21. 
  
  
  
  21.     } 
    22. 
  
  
  
  22.     cout << endl; 
    23. 
  
  
  
  23. } 
    24. 
  
  
  
  24. bool detectLoop(Node* head) 
    25. 
  
  
  
  25. { 
    26. 
  
  
  
  26.     Node* temp = new Node; 
    27. 
  
  
  
  27.     while (head != NULL) { 
    28. 
  
  
  
  28.         if (head->next == NULL) { 
    29. 
  
  
  
  29.             return false; 
    30. 
  
  
  
  30.         } 
    31. 
  
  
  
  31.         if (head->next == temp) { 
    32. 
  
  
  
  32.             return true; 
    33. 
  
  
  
  33.         } 
    34. 
  
  
  
  34.         Node* nex = head->next; 
    35. 
  
  
  
  35.         head->next = temp; 
    36. 
  
  
  
  36.         head = nex; 
    37. 
  
  
  
  37.     } 
    38. 
  
  
  
  38.   
    39. 
  
  
  
  39.     return false; 
    40. 
  
  
  
  40. } 
    41. 
  
  
  
  41. int main() 
    42. 
  
  
  
  42. { 
    43. 
  
  
  
  43.     Node* head = newNode(1); 
    44. 
  
  
  
  44.     head->next = newNode(2); 
    45. 
  
  
  
  45.     head->next->next = newNode(3); 
    46. 
  
  
  
  46.     head->next->next->next = newNode(4); 
    47. 
  
  
  
  47.     head->next->next->next->next = newNode(5); 
    48. 
  
  
  
  48.     head->next->next->next->next->next = head->next->next; 
    49. 
  
  
  
  49.   
    50. 
  
  
  
  50.     bool found = detectLoop(head); 
    51. 
  
  
  
  51.     if (found) 
    52. 
  
  
  
  52.         cout << "Loop Found"; 
    53. 
  
  
  
  53.     else 
    54. 
  
  
  
  54.         cout << "No Loop"; 
    55. 
  
  
  
  55.   
    56. 
  
  
  
  56.     return 0; 
    57. 
  
  
  
  57. } 
    58.

复杂度分析：

时间复杂度： O（n）。
只需循环一次即可。

辅助空间： O（1）。
不需要空间。

解决方案5：存放长度

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

 
 
 
    
  
  
  
  1. #include  
    2. 
  
  
  
  2. using namespace std; 
    3. 
  
  
  
  3.   
    4. 
  
  
  
  4. struct Node { 
    5. 
  
  
  
  5.     int key; 
    6. 
  
  
  
  6.     struct Node* next; 
    7. 
  
  
  
  7. }; 
    8. 
  
  
  
  8.   
    9. 
  
  
  
  9. Node* newNode(int key) 
    10. 
  
  
  
  10. { 
    11. 
  
  
  
  11.     Node* temp = new Node; 
    12. 
  
  
  
  12.     temp->key = key; 
    13. 
  
  
  
  13.     temp->next = NULL; 
    14. 
  
  
  
  14.     return temp; 
    15. 
  
  
  
  15. } 
    16. 
  
  
  
  16. void printList(Node* head) 
    17. 
  
  
  
  17. { 
    18. 
  
  
  
  18.     while (head != NULL) { 
    19. 
  
  
  
  19.         cout << head->key << " "; 
    20. 
  
  
  
  20.         head = head->next; 
    21. 
  
  
  
  21.     } 
    22. 
  
  
  
  22.     cout << endl; 
    23. 
  
  
  
  23. } 
    24. 
  
  
  
  24. int distance(Node* first, Node* last) 
    25. 
  
  
  
  25. { 
    26. 
  
  
  
  26.     int counter = 0; 
    27. 
  
  
  
  27.   
    28. 
  
  
  
  28.     Node* curr; 
    29. 
  
  
  
  29.     curr = first; 
    30. 
  
  
  
  30.   
    31. 
  
  
  
  31.     while (curr != last) { 
    32. 
  
  
  
  32.         counter += 1; 
    33. 
  
  
  
  33.         curr = curr->next; 
    34. 
  
  
  
  34.     } 
    35. 
  
  
  
  35.   
    36. 
  
  
  
  36.     return counter + 1; 
    37. 
  
  
  
  37. } 
    38. 
  
  
  
  38. bool detectLoop(Node* head) 
    39. 
  
  
  
  39.     Node* temp = new Node; 
    40. 
  
  
  
  40.   
    41. 
  
  
  
  41.     Node *first, *last; 
    42. 
  
  
  
  42.     first = head; 
    43. 
  
  
  
  43.     last = head; 
    44. 
  
  
  
  44.     int current_length = 0; 
    45. 
  
  
  
  45.     int prev_length = -1; 
    46. 
  
  
  
  46.   
    47. 
  
  
  
  47.     while (current_length > prev_length && last != NULL) { 
    48. 
  
  
  
  48.           prev_length = current_length; 
    49. 
  
  
  
  49.         current_length = distance(first, last); 
    50. 
  
  
  
  50.         last = last->next; 
    51. 
  
  
  
  51.     } 
    52. 
  
  
  
  52.       
    53. 
  
  
  
  53.     if (last == NULL) { 
    54. 
  
  
  
  54.         return false; 
    55. 
  
  
  
  55.     } 
    56. 
  
  
  
  56.     else {  
    57. 
  
  
  
  57.         return true; 
    58. 
  
  
  
  58.     } 
    59. 
  
  
  
  59. } 
    60. 
  
  
  
  60. int main() 
    61. 
  
  
  
  61. { 
    62. 
  
  
  
  62.     Node* head = newNode(1); 
    63. 
  
  
  
  63.     head->next = newNode(2); 
    64. 
  
  
  
  64.     head->next->next = newNode(3); 
    65. 
  
  
  
  65.     head->next->next->next = newNode(4); 
    66. 
  
  
  
  66.     head->next->next->next->next = newNode(5); 
    67. 
  
  
  
  67.     head->next->next->next->next->next = head->next->next; 
    68. 
  
  
  
  68.   
    69. 
  
  
  
  69.     bool found = detectLoop(head); 
    70. 
  
  
  
  70.     if (found) 
    71. 
  
  
  
  71.         cout << "Loop Found"; 
    72. 
  
  
  
  72.     else 
    73. 
  
  
  
  73.         cout << "No Loop Found"; 
    74. 
  
  
  
  74.   
    75. 
  
  
  
  75.     return 0; 
    76. 
  
  
  
  76. } 
    77.

}

当前文章：五个解决办法教你C++中检测链表中的循环
本文网址：http://www.mswzjz.cn/qtweb/news7/29907.html

攀枝花网站建设、攀枝花网站运维推广公司-贝锐智能，是专注品牌与效果的网络营销公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 贝锐智能

贝锐智能技术为您推荐以下文章

网站维护知识

分类信息网

成都木托盘　　 　定制网站设计　　 　成都微商城　　 　西信中心　　 　网站改版　　 　成都app软件开发公司　　 　IDC机房托管　　 　温江网站建设　　 　工商财税　　 　成都光华机房　　 　乐山网站建设　　 　成都400电话　　 　绵阳服务器托管　　 　成都logo设计标志　　 　成都娃娃鱼　　 　Google外贸推广　　 　虚拟主机购买　　 　艾名斯线缆　　 　租用服务器　　 　大英网站建设