备案控制台
探索云世界
开发者社区 云计算 文章 正文

解决单链表中的环问题

2017-10-04 983
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：

 给定一个单链表，只给出头指针h：

  1. 如何判断是否存在环？
  2. 如何知道环的长度？
  3. 如何找出环的连接点在哪里？
  4. 带环链表的长度是多少？

 

问题1   如何判断是否有环

使用追赶的方法，设定两个指针slow、fast，从头指针开始，每次分别前进1步、2步。如存在环，则两者相遇；如不存在环，fast遇到NULL退出。

clip_image001[6]clip_image002[6]clip_image003[6]clip_image004[6]clip_image005[6]clip_image006[6]clip_image007[10]clip_image008[6]clip_image009[18] 

clip_image010[6]clip_image007[11] 

clip_image011[6]clip_image012[6]clip_image009[19]clip_image009[20]clip_image009[21]slow fast

 

问题2   如何判断环的长度

在相遇点出同时出发，fast指针和slow指针再次相遇时，slow指针走过的点的个数就是环的长度。试问会不会slow在不到一圈的地方两者相遇呢？不会，因为假设slow走s,则fast走2s。二者相遇则二者距离必相差圈数的倍数，即：2s-s = k*圈距离=s。此时k=1。因此得出结论：从相遇到再次相遇，slow再走完整的一圈。

 

问题3   如何找出环的连接点

定理：碰撞点p到连接点的距离=头指针到连接点的距离，因此，分别从碰撞点、头指针开始走，相遇的那个点就是连接点。

clip_image013[6]clip_image014[6]                                                                

证明：

链表形状类似数字6。  
假设甩尾（在环外）长度为 a（结点个数），环内长度为 b 。  
则总长度（也是总结点数）为 a+b 。  
从头开始，0 base 编号。  
将第 i 步访问的结点用 S(i) 表示。i = 0, 1 ... 
当 i＜a 时，S(i)=i ；  
当 i≥a 时，S(i)=a+(i-a)%b 。

分析追赶过程。  
两个指针分别前进，假定经过 x 步后，碰撞。则有：S(x)=S(2x) 
由环的周期性有：2x=tb+x 。得到 x=tb 。  
另，碰撞时，必须在环内，不可能在甩尾段，有 x>=a 。

连接点为从起点走 a 步，即 S(a)。  
S(a) = S(tb+a) = S(x+a)。  
得到结论：从碰撞点 x 前进 a 步即为连接点。

根据假设易知 S(a-1) 在甩尾段，S(a) 在环上，而 S(x+a) 必然在环上。所以可以发生碰撞。 又，同为前进 a 步，同为连接点，所以必然发生碰撞。

综上，从 x 点和从起点同步前进，第一个碰撞点就是连接点。

 

问题4   带环链表的长度是多少

问题2知道环的长度，问题3知道环外边的长度。两者相加即为总长度。

 

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <stdlib.h>
#include <stdio.h>
 
typedef  struct  node
{
     int  data;
     struct  node *next;
}node;
 
node *Create_list()    //建立链表
{
     node *p_return, *p;
     p_return = NULL;
 
     node *n1 = (node *) malloc ( sizeof (node));
     n1->data = 1;
     n1->next = NULL;
     p = n1;
     p_return = p;
 
     node *n2 = (node *) malloc ( sizeof (node));
     n2->data = 2;
     n2->next = NULL;
     p->next = n2;
     p = n2;
 
     node *n3 = (node *) malloc ( sizeof (node));
     n3->data = 3;
     n3->next = NULL;
     p->next = n3;
     p = n3;
 
     node *n4 = (node *) malloc ( sizeof (node));
     n4->data = 4;
     n4->next = NULL;
     p->next = n4;
     p = n4;
 
     node *n5 = (node *) malloc ( sizeof (node));
     n5->data = 5;
     n5->next = NULL;
     p->next = n5;
     p = n5;
 
     node *n6 = (node *) malloc ( sizeof (node));
     n6->data = 6;
     n6->next = NULL;
     p->next = n6;
     p = n6;
 
     p->next = n3;
 
     return  p_return;
}
 
node *find_in_node(node *p1, node *p2)    //找到入环的结点
{
     while (p1 != p2)
     {
         p1 = p1->next;
         p2 = p2->next;
     }
     return  p1;
}
int  get_out_len(node *p1, node *p2)    //计算出环外边的长度
{
     int  num = 0;
     while (p1 != p2)
     {
         p1 = p1->next;
         p2 = p2->next;
         num++;
     }
     return  num;
}
 
node *check_loop(node *p)   //检查是否有环
{
     node *p_slow, *p_fast;
     p_slow = p;
     p_fast = p;
     int  tag = 0;
     while (p_slow && p_fast->next)
     {
         p_slow = p_slow->next;
         p_fast = p_fast->next->next;
         if (p_slow == p_fast)
         {
             tag = 1;
             break ;
         }
     }
     if (tag == 1)
     {
         printf ( "Have loop\n" );
         return  p_slow;
     }
     else
     {
         printf ( "Not have loop\n" );
         return  NULL;
     }
}
int  get_len_loop(node *var_loop)    //得出环的长度
{
     node *p = var_loop->next;
     int  num = 1;
     while (p != var_loop)
     {
         p = p->next;
         num++;
     }
     return  num;
}
 
int  main()
{
     node *p = Create_list();
     node *coin_loop = check_loop(p);
     if (coin_loop)
     {
         int  len_loop = get_len_loop(coin_loop);
         printf ( "Length of Loop is:%d\n" , len_loop);
         node *in_node = find_in_node(p, coin_loop);
         int  len_out = get_out_len(p, coin_loop);
         printf ( "Length of out Loop is %d\n" , len_out);
         printf ( "Length of all is %d\n" , len_out + len_loop);
     }
}

 


本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/p/3395347.html，如需转载请自行联系原作者


技术mix呢
目录
相关文章
张继群
|
19天前
|
存储 算法 C语言
线性表，双向链表，静态链表，循环链表(约瑟夫环)（上）
线性表，双向链表，静态链表，循环链表(约瑟夫环)
张继群
39 5
醋溜马桶圈
|
4月前
快慢指针之：链表中倒数第k个结点
快慢指针之：链表中倒数第k个结点
醋溜马桶圈
38 0
西柚与蓝莓
|
11天前
|
算法 C语言 索引
环形链表（快慢指针）
环形链表（快慢指针）
西柚与蓝莓
12 1
张继群
|
19天前
|
存储 C语言
线性表，双向链表，静态链表，循环链表(约瑟夫环)（下）
线性表，双向链表，静态链表，循环链表(约瑟夫环)
张继群
32 6
Dream_Chaser～
|
6月前
|
索引
【链表OJ】相交链表 环形链表1
【链表OJ】相交链表 环形链表1
Dream_Chaser～
22 0
小白在努力jy
|
8月前
[链表OJ题 2] 链表的中间结点 -- 快慢指针找链表的中间节点
[链表OJ题 2] 链表的中间结点 -- 快慢指针找链表的中间节点
小白在努力jy
43 0
阿熊不会编程
|
4月前
|
机器学习/深度学习 存储 缓存
有环链表环的问题
有环链表环的问题
阿熊不会编程
21 0
风正豪
|
8月前
|
存储
利用快慢指针，求链表的中间结点，判断链表是否是环形链表
利用快慢指针，求链表的中间结点，判断链表是否是环形链表
风正豪
34 0
Jambo!
|
10月前
链表带环问题
链表带环问题
Jambo!
82 0
游客ufqubef22u3cg
|
10月前
|
算法
【基础算法】单链表的OJ练习(2) # 链表的中间结点 # 链表中倒数第k个结点 #
【基础算法】单链表的OJ练习(2) # 链表的中间结点 # 链表中倒数第k个结点 #
游客ufqubef22u3cg
145 0
为什么选择阿里云什么是云计算全球基础设施技术领先稳定可靠安全合规分析师报告
产品和定价全部产品免费试用产品动态产品定价价格计算器云上成本管理
解决方案技术解决方案
文档与社区文档开发者社区天池大赛培训与认证
权益中心免费试用高校计划企业扶持计划推荐返现计划
支持与服务基础服务企业增值服务迁云服务官网公告健康看板信任中心
关注阿里云
关注阿里云公众号或下载阿里云APP，关注云资讯，随时随地运维管控云服务
阿里云APP阿里云微信
联系我们：4008013260
法律声明Cookies政策廉正举报安全举报联系我们加入我们
阿里巴巴集团淘宝网天猫全球速卖通阿里巴巴国际交易市场1688阿里妈妈飞猪阿里云计算AliOS万网高德UC友盟优酷钉钉支付宝达摩院淘宝海外阿里云盘饿了么
© 2009-2024 Aliyun.com 版权所有 增值电信业务经营许可证： 浙B2-20080101 域名注册服务机构许可： 浙D3-20210002 京D3-20220015
浙公网安备 33010602009975号浙B2-20080101-4