问题描述:在单向链表中,每个结点都包含一个指向下一个结点的指针,最后一个结点的这个指针被设置为空。但如果把最后一个结点的指针指向链表中存在的某个结点,就会形成一个环,在顺序遍历链表的时候,程序就会陷入死循环。我们的问题就是,如何检测一个链表中是否有环,如果检测到环,如何确定环的入口点(即求出环长,环前面的链长)。
一种比较耗空间的做法是,从头开始遍历链表,把每次访问到的结点(或其地址)存入一个集合(hashset)或字典(dictionary),如果发现某个结点已经被访问过了,就表示这个链表存在环,并且这个结点就是环的入口点。这需要O(N)空间和O(N)时间,其中N是链表中结点的数目。
如果要求只是用O(1)空间、O(N)时间,应该怎么处理呢?
其实很简单,想象一下在跑道上跑步:两个速度不同的人在操场跑道上一圈一圈地跑,他们总会有相遇的时候。因此我们只需要准备两个指针,同时从链表头出发,一个每次往前走一步,另一个每次往前走两步。如果链表没有环,那么经过一段时间,第二个(速度较快的)指针就会到达终点;但如果链表中有环,两个指针就会在环里转圈,并会在某个时刻相遇。
大家也许会问,这两个指针要在环里转多少圈才能相遇呢?会不会转几千几万圈都无法相遇?实际上,第一个(速度慢的)指针在环里转满一圈之前,两个指针必然相遇。不妨设环长为L,第一个指针P1第一次进入环时,第二个指针P2在P1前方第a个结点处(0 < a < L),设经过x次移动后两个指针相遇,那么应该有0 + x = a + 2x (mod L),显然x = L - a。下面这张图可以清晰地表明这种关系,经过x = L - a次移动,P1向前移动了L - a个位置(相当于后退了a),到达P1′处,而P2向前移动了2L - 2a个位置(相当于后退了2a),到达P2′处,显然P1′和P2′是同一点。
在知道链表内有环后,求环长是一件非常简单的事情,只要从刚才那个相遇点开始,固定P2,继续移动P1,直到P1与P2再次相遇,所经过的步数就是环长。
怎么求环前面那段子链的长度呢?很简单,让P1和P2都回到链表起点,然后让P2先往前走L次(每次往前走一步),然后P1和P2再同时往前走,当它们再次相遇时,P1所走的步数就是环前面的子链长度。
算法示意:
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 |
def CheckRing(head):
l1 = 0 # length of the chain before the ring
l2 = 0 # length of the ring
# Check if there is a ring.
pos1 = head
pos2 = head
while pos2 and pos2.next:
pos1 = pos1.next
pos2 = pos2.next.next
l1 += 2
if pos2 and pos1 == pos2:
l2 = 1
break
if not l2:
if pos2: l1 += 1
return (l1, l2) # l2 should be 0
# Calc the length of the ring.
pos1 = pos2.next
while pos1 != pos2:
pos1 = pos1.next
l2 += 1
# Calc the length of the chain before the ring.
l1 = 0
pos1 = head
pos2 = head
for i in xrange(l2):
pos2 = pos2.next
while pos1 != pos2:
pos1 = pos1.next
pos2 = pos2.next
l1 += 1
return (l1, l2)
|
转载 http://www.gocalf.com/blog/circle-of-link-list.html
相关推荐
C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表
c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,
1.随机产生或键盘输入一组元素,建立一个带头结点的单向链表(无序)。 2.遍历单向链表。 3.把单向链表中元素逆置(不允许申请新的结点空间)。 4.在单向链表中删除所有的偶数元素结点。 5.编写在非递减...
单向循环链表实现约瑟夫环.zip
04.单向链表以及单向链表的应用.ppt
C#单向链表的实现的源码
一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向的下一个人开始重新从1报数,如此下去,直到所有人全部...
单向链表架构代码,适合学习链表的学生学习!内附排序函数,打印函数,链表尾添项函数,删除函数。
单链表实现双向循环链表单向链表存在一个弊端就是,当需要获取某个结点p的前驱时,需要从头指针开始遍历链表,获得“前驱”的执行时间为O(n),为了克服单向链表的这种缺点,可以利用双向链表。在双向链表中有两个...
使用单向链表对字符串进行排序,并以从小到大的顺序显示出来。
这是一个单向链表,它具有插入与删除节点的功能。Entry类实现了链表的各节点。
Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现单向链表Java SE程序 类实现...
将一个单向链表反向连接
用C语言编写的约瑟夫环问题解决程序,利用单向循环链表存储结构模拟此过程
本文件描述单向链表类模板。移植时,仅需要本文件
培训班老师自己写的单向链表,代码非常全,也很好理解,可执行。
每敲一次代码都会有新的收获,基本功不扎实啥也干不了。单向链表的插入,删除,创建,遍历是数据结构的基本操作。里边的算法值得学习。下面我们就来学习一下单向链表结点的逐个删除的方法。
VC++采用单向循环链表实现约瑟夫环,希望和大家共勉。
分别用C和C++实现了单向链表(创建链表,插入数据、获取指定位置的数据、删除指定位置的数据...),如果在使用中觉得api不够用可以进行扩展;其中包含测试。
java语言模拟单向链表,JAVA数据结构