C++语言判断单链表是否有环链表 程序源码

[复制链接]
查看211 | 回复0 | 2021-11-15 17:07:19 | 显示全部楼层 |阅读模式
1.问题:如果给定一个单链表,如何判断其是否为有环链表
2.方法:
(1)从给定链表的第一个节点开始遍历,每遍历至一个节点,都将其和所有的前驱节点进行比对,如果为同一个节点,则表明当前链表中有环;反之,如果遍历至链表最后一个节点,仍未找到相同的节点,则证明该链表中无环。
112215vqiz0ywa4ghyktkq.png

如上所示,当函数的返回值为 True,表示该链表有环;反之若函数返回值为 False,表明链表中无环。显然,此实现方案的时间复杂度为O(n2)。
(2)在一个链表中,如果 2 个指针(假设为 H1 和 H2)都从表头开始遍历链表,其中 H1 每次移动 2 个节点的长度(H1 = H1->next->next),而 H2 每次移动 1 个节点的长度(H2 = H2->next),如果该链表为有环链表,则 H1、H2 最终必定会相等;反之,如果该链表中无环,则 H1、H2 永远不会相遇。
112437ma8ek4bzlx9wt22i.png

本算法的时间复杂度为 O(n)。
源码:
  1. #include<stdio.h>
  2. #include<stdlib.h>

  3. //自定义 bool 类型
  4. typedef enum Bool
  5. {
  6.     False=0,
  7.     True=1
  8. }Bool;

  9. typedef struct link{
  10.     int data;
  11.     struct link* next;
  12. }link;

  13. link *linkIint(int n)
  14. {
  15.     link *head=(link*)malloc(sizeof(link));
  16.     head->data=1;
  17.     head->next=NULL;
  18.     link *phead=head;
  19.     int i;
  20.     for(i=2;i<=n;i++)
  21.     {
  22.         link *temp=(link*)malloc(sizeof(link));
  23.         temp->data=i;
  24.         temp->next=NULL;

  25.         head->next=temp;
  26.         head=head->next;
  27.     }
复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则