赞
踩
给定一个单向链表,请判断该链表是否存在环;如果存在的话,请找到环的起点。
重要
注1:为了描述方便,后文中除非特殊指定,否则将“单向链表”简称为“链表”
注2:本文以包含头结点的链表为例,如果是一个不含头结点的链表,因为起始位置不同,所以一些变量的定义会受到影响,但不影响本文讨论的解题方法
一般情况下,一个链表存在一个尾结点,该结点的next
指针为空。然而,当一个链表的尾结点指向了之前的某个前序结点时,链表就出现了“环”:
本题就是要判断一个给定的链表是否存在环,并找到环开始的位置。
注:严格来说,有环链表是没有尾结点的,因为不存在“最后一个结点”。但后文为了描述方便,仍然将指向环首结点的这个结点称为尾结点。
可以通过快慢指针来判断一个链表是否有环。
在一个链表的头结点处设置两个指针slow
和fast
并同时向前移动,规定slow
每次移动一个结点,fast
每次移动两个结点,这就是快慢指针。
如果链表不存在环,则肯定存在一个结点,其next
指针为空,所以,只要fast
在移动过程中遇到了空结点,则证明链表不存在环。
如果链表存在环,那么,因为fast
移动速度比slow
要快,所以,一定会在某些时刻,fast
会从后面追上slow
。问题在于:fast
和slow
一定会相遇吗?是否存在fast
直接跳过slow
的情况?答案是一定会相遇,而且每次fast
追上slow
时,都必定相遇!证明如下:
假设在第
n
次移动后,fast
来到了slow
之前,在第n+1
次移动后,fast
在slow
之后,即:
{ f a s t n = s l o w n − 1 ( 1 ) f a s t n + 1 = s l o w n + 1 + 1 ( 2 ) {fastn=slown−1 (1)fastn+1=slown+1+1 (2) {fastn=slown−1 (1)fastn+1=slown+1+1 (2)
而根据fast
和slow
的定义:
{ f a s t n + 1 = f a s t n + 2 ( 3 ) s l o w n + 1 = s l o w n + 1 ( 4 ) {fastn+1=fastn+2 (3)slown+1=slown+1 (4) {fastn+1=fastn+2 (3)slown+1=slown+1 (4)
将3
和4
代入2
,得到:
f a s t n + 2 = s l o w n + 1 + 1 f a s t n = s l o w n fastn+2=slown+1+1fastn=slown fastn+2fastn=slown+1+1=slown
这与等式1
产生了矛盾,所以假设不成立。那么,既然fast
终将超过slow
,又不可能直接跳过它,所以,就只能踩着它过去了。
既然在有环的链表中fast
与slow
一定会相遇,那就可以利用这个特性来检测有环链表,即:fast
遇到空结点,表明链表无环;fast
遇到slow
结点,表明链表有环。
毫无疑问,快慢指针在有环链表中如果一直移动下去,则会反复相遇,而且,因为相遇时两个指针位于同一结点,所以此时它们相对于环的起点位移相同。
假设,环首结点之前的链表长度为
K
(
K
>
=
0
)
K(K>=0)
K(K>=0),环的长度为
L
(
L
>
=
2
)
L(L>=2)
L(L>=2),快慢指针相遇时,慢指针走过的总距离为
d
(
d
>
K
)
d(d>K)
d(d>K),快指针走过的总距离为
2
d
2d
2d。
那么相遇时,根据相对于环的起点位移相同,有如下关系:
d
−
K
=
(
2
d
−
K
)
−
m
L
(
d
>
K
,
m
∈
N
+
)
d-K=(2d-K)-mL ~~~~(d>K,m\in N^+)
d−K=(2d−K)−mL (d>K,m∈N+)
m
L
mL
mL其实就是完整跑完
n
n
n次环的距离。上式整理得到:
d
=
m
L
(
d
>
K
,
m
∈
N
+
)
d=mL ~~~~(d>K,m \in N^+)
d=mL (d>K,m∈N+)
那么,求首次相遇的位置也就是找满足条件的最小
d
d
d或是最小
m
m
m。因为
d
>
K
d>K
d>K,也即
m
L
>
K
mL>K
mL>K,那么,有如下三种情况:
综上,快慢指针首次相遇的位置,一定是在慢指针首次进入环和尾结点之间的位置(包括尾结点)。
通过上面的步骤,找到快慢指针首次相遇的结点后,将该结点标记为p2
,并将链表头结点标记为p1
。如果p1
和p2
同时向前移动,每次各前进一个结点,它们未来会相遇吗?
由于两个结点移动速度相同,那么当它们都位于一条没有分叉的路上时,就不可能相遇,所以,唯一的相遇机会就是p1
首次来到环首结点之前,p2
也刚好来到了尾结点,这样在下一时刻,它们两个就可以在环首结点相遇了。
现在延用上面步骤中对
K
,
L
K,L
K,L的定义,并重新定义
d
d
d为p1
到p2
的直接距离(其实就是上面的min(d)
,即首次相遇的位置)。假设p1
和p2
能够相遇,则相遇时p1
走动的距离为
K
K
K,p2
走动的距离也为
K
K
K
那么,相遇的条件可以定义为:p2
在走动
K
K
K距离后位于尾结点,写成等式如下:
K
+
(
d
−
K
)
=
n
L
(
d
>
K
,
n
∈
N
+
)
K+(d-K)=nL~~~(d>K, n\in N^+)
K+(d−K)=nL (d>K,n∈N+)
(
d
−
K
)
(d-K)
(d−K)是初始时p2
到环首结点的距离。等式变换后:
d
=
n
L
(
d
>
K
,
n
∈
N
+
)
d=nL~~~(d>K,n\in N^+)
d=nL (d>K,n∈N+)
由于当前是基于前面快慢指针相遇的情况来讨论的,所以前面的结论就是当前的已知条件;又因为
d
d
d就是前面的
m
i
n
(
d
)
min(d)
min(d),所以,
n
L
nL
nL等于
m
L
mL
mL;又因为
n
n
n和
m
m
m的定义域相同,所以存在
n
n
n,且
n
=
m
n=m
n=m。
综上,假设成立,所以p1
和p2
将相遇在环的起点。
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。