AI 助理
备案控制台
开发者社区 云计算 文章 正文

解决单链表中的环问题

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

 给定一个单链表，只给出头指针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呢
目录
相关文章
张继群
|
7月前
|
存储 算法 C语言
线性表，双向链表，静态链表，循环链表(约瑟夫环)（上）
线性表，双向链表，静态链表，循环链表(约瑟夫环)
张继群
85 5
兀码
|
7月前
|
缓存 测试技术
有环链表的处理
【5月更文挑战第7天】该文介绍了链表环的检测和处理方法。使用快慢指针可判断链表是否存在环，相遇点距离等于环入口距离。环的长度可通过相遇时慢指针的步长计算。若两链表相交，它们的尾节点相同。
兀码
50 1
有环链表的处理
张继群
|
7月前
|
存储 C语言
线性表，双向链表，静态链表，循环链表(约瑟夫环)（下）
线性表，双向链表，静态链表，循环链表(约瑟夫环)
张继群
77 6
小白在努力jy
[链表OJ题 2] 链表的中间结点 -- 快慢指针找链表的中间节点
[链表OJ题 2] 链表的中间结点 -- 快慢指针找链表的中间节点
小白在努力jy
60 0
阿熊不会编程
|
机器学习/深度学习 存储 缓存
有环链表环的问题
有环链表环的问题
阿熊不会编程
53 0
风正豪
|
存储
利用快慢指针，求链表的中间结点，判断链表是否是环形链表
利用快慢指针，求链表的中间结点，判断链表是否是环形链表
风正豪
61 0
游客ufqubef22u3cg
|
算法
【基础算法】单链表的OJ练习(2) # 链表的中间结点 # 链表中倒数第k个结点 #
【基础算法】单链表的OJ练习(2) # 链表的中间结点 # 链表中倒数第k个结点 #
游客ufqubef22u3cg
177 0
vblltq7lxmh76
|
API
链表——单链表的反转
单链表的反转就是从原链表的第一个存 数据的结点开始,依次递归调用反转每一个结点，直到把最后一个结点反转完毕
vblltq7lxmh76
123 0
链表——单链表的反转
董员外
通过快慢指针来解决链表中倒数第k个节点的问题
通过快慢指针来解决链表中倒数第k个节点的问题
董员外
142 0
通过快慢指针来解决链表中倒数第k个节点的问题
6sqzjcuyfhfwi
判断链表是否存在环——快慢指针
判断链表是否存在环——快慢指针
6sqzjcuyfhfwi
120 0
判断链表是否存在环——快慢指针

热门文章

最新文章

  • 1
    跟阿里云技术专家阙寒一起深度了解视频直播CDN技术
  • 2
    流批一体的近实时数仓的思考与设计
  • 3
    丰富、连接、待集成—MaxCompute 生态再出发
  • 4
    securecrt克隆会话与sshd 的 MaxSessions
  • 5
    Flink 消息聚合处理方案
  • 6
    VMware安装的相关文章
  • 7
    forever让nodejs应用后台执行
  • 8
    路边的烧烤摊杂感
  • 9
    size_type、size_t、differentce_type以及ptrdiff_t
  • 10
    一些链接
  • 1
    《人工智能知识图谱构建与应用的最新突破与成果》
    37
  • 2
    《零样本学习：突破瓶颈，开启智能新征程》
    25
  • 3
    《知识表示：开启人工智能学习与推理的密钥》
    27
  • 4
    《信息传播：人工智能助力驱散虚假信息阴霾》
    28
  • 5
    《多模态融合：开启智能新时代的钥匙》
    36
  • 6
    自学记录鸿蒙 API 13：实现人脸检测 Core Vision Face Detector
    66
  • 7
    阿里云先知安全沙龙(武汉站) ——AI赋能软件漏洞检测，机遇, 挑战与展望
    514
  • 8
    在线使用：Poe Ai网页版_pc版_poe ai中文官网入口
    21
  • 9
    java项目中jar启动执行日志报错：no main manifest attribute, in /www/wwwroot/snow-server/z-server.jar-jar打包的大小明显小于正常大小如何解决
    39
  • 10
    新手指南：人工智能poe ai 怎么用？国内使用poe记住这个方法就够了！
    34

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    手把手教你白嫖阿里云服务器(免费领服务器)