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

1.问题：如果给定一个单链表，如何判断其是否为有环链表
2.方法：
（1）从给定链表的第一个节点开始遍历，每遍历至一个节点，都将其和所有的前驱节点进行比对，如果为同一个节点，则表明当前链表中有环；反之，如果遍历至链表最后一个节点，仍未找到相同的节点，则证明该链表中无环。


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


本算法的时间复杂度为 O(n)。
源码：

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. 
   
4. //自定义 bool 类型
   
5. typedef enum Bool
   
6. {
   
7.     False=0,
   
8.     True=1
   
9. }Bool;
   
10. 
    
11. typedef struct link{
    
12.     int data;
    
13.     struct link* next;
    
14. }link;
    
15. 
    
16. link *linkIint(int n)
    
17. {
    
18.     link *head=(link*)malloc(sizeof(link));
    
19.     head->data=1;
    
20.     head->next=NULL;
    
21.     link *phead=head;
    
22.     int i;
    
23.     for(i=2;i<=n;i++)
    
24.     {
    
25.         link *temp=(link*)malloc(sizeof(link));
    
26.         temp->data=i;
    
27.         temp->next=NULL;
    
28. 
    
29.         head->next=temp;
    
30.         head=head->next;
    
31.     }

复制代码

【必读】版权免责声明

1、本主题所有言论和内容纯属会员个人意见，与本论坛立场无关。2、本站对所发内容真实性、客观性、可用性不做任何保证也不负任何责任，网友之间仅出于学习目的进行交流。3、对提供的数字内容不拥有任何权利，其版权归原著者拥有。请勿将该数字内容进行商业交易、转载等行为，该内容只为学习所提供，使用后发生的一切问题与本站无关。 4、本网站不保证本站提供的下载资源的准确性、安全性和完整性;同时本网站也不承担用户因使用这些下载资源对自己和他人造成任何形式的损失或伤害。 5、本网站所有软件和资料均为网友推荐收集整理而来，仅供学习用途使用，请务必下载后两小时内删除，禁止商用。6、如有侵犯你版权的，请及时联系我们（电子邮箱1370723259@qq.com）指出，本站将立即改正。