LeetCode 142. 环形链表 II
题目描述
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 n u l l null null。
为了表示给定链表中的环，我们使用整数 p o s pos pos 来表示链表尾连接到链表中的位置（索引从 0 0 0 开始）。 如果 p o s pos pos 是 − 1 -1 −1，则在该链表中没有环。注意， p o s pos pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
示例 1：
输入：
h
e
a
d
=
[
3
,
2
,
0
,
−
4
]
,
p
o
s
=
1
head = [3,2,0,-4], pos = 1
head=[3,2,0,−4],pos=1
输出：返回索引为
1
1
1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：
h
e
a
d
=
[
1
,
2
]
,
p
o
s
=
0
head = [1,2], pos = 0
head=[1,2],pos=0
输出：返回索引为
0
0
0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：
h
e
a
d
=
[
1
]
,
p
o
s
=
−
1
head = [1], pos = -1
head=[1],pos=−1
输出：返回
n
u
l
l
null
null
解释：链表中没有环。
提示：
链表中节点的数目范围在范围
[
0
,
104
]
[0, 104]
[0,104] 内
−
105
<
=
N
o
d
e
.
v
a
l
<
=
105
-105 <= Node.val <= 105
−105<=Node.val<=105
p
o
s
pos
pos 的值为
−
1
-1
−1 或者链表中的一个有效索引
题目分析
关于环形链表
首先我们一般接触的链表是单链表有表尾，并且表尾结点的 n e x t next next 指针域是指向 N U L L NULL NULL 的。
那么如何判断一个链表是否有环呢？我们可以现从生活的一个例子来思考：
假设有
A
A
A 同学和
B
B
B 同学在操场上跑步，如果他们跑的都是直道，并且
B
B
B 同学的跑步速度大于
A
A
A 同学的跑步速度，那么在到达终点之前，他们两个都不可能相遇。
但是，如果是在环形跑道上跑步的话，那么
A
A
A 同学和
B
B
B 同学同时开始跑的时候，总有一个时刻，
A
A
A 和
B
B
B 同学会相遇，并且
B
B
B 同学比
A
A
A 同学多跑了整数圈（具体整数多少取决于
B
B
B 同学的跑步速度）
对于链表来说，我们可以先设置两个指针指向头指针指向的结点，然后一个指针是快指针，一个指针是慢指针，它们分别代表
B
B
B 同学和
A
A
A 同学。然后我们设置快指针的速度是每次移动两个结点，而慢指针的速度是每次移动一个结点，也就代表了快指针的移动速度大于慢指针。
- 当链表没有环的时候，快指针一定会首先到达表尾或者是 N U L L NULL NULL 就好像上图直道跑步中， B B B 同学首先到达终点一样。
- 当链表有环的时候，那么根据上面的分析，快指针和慢指针一定会在某一个结点相遇，指向同一个结点，就像上图分析弯道跑步一样会在某一个时刻相遇。
关于入环口
假设有 A A A 同学和 B B B 同学从起点开始跑步，然后他们在首次相遇点相遇，如下图所示：
我们假设：
- 起点到入环口的距离为 D D D.
- 入环口到首次相遇点的距离为 S 1 S_1 S1.
- 首次相遇点到入环口的距离为 S 2 S_2 S2.
又因为当
A
A
A 同学和
B
B
B 同学第一次相遇的时候，他们所经过的时间是相同的，而且
B
B
B 同学多跑了
n
n
n 圈
(
n
≥
1
)
(n\ge1)
(n≥1)
又因为
V
B
=
2
V_B = 2
VB=2 ,
V
A
=
1
V_A = 1
VA=1,所以可以得出以下等式成立：
经过整理得：
以上表达式可以告诉我们：
- 如果 A A A 同学从起点开始走， B B B 同学从首次相遇点开始走，并且他们的速度都是匀速的。
- 当 B B B 同学走了 S 2 S_2 S2距离到达入环口的时候， A A A 同学也走了 S 2 S_2 S2 距离，而且 A A A 同学还剩 ( D − S 2 ) (D-S_2) (D−S2) 距离，根据以上等式也就是 ( n − 1 ) ( S 1 + S 2 ) (n-1)(S_1+S_2) (n−1)(S1+S2) 的距离。
- 所以当 A A A 同学继续往前走到达入环口的时候， B B B 同学一定从入环口走 ( n − 1 ) ( S 1 + S 2 ) (n-1)(S_1+S_2) (n−1)(S1+S2) 的距离再次到达入环口。因此这两个同学就在入环口相遇了。
算法分析
根据以上两个讨论，我们可以总结归纳出以下的算法：
- 首先用 f a s t fast fast 指针和 s l o w slow slow 指针都指向 h e a d head head 指向的第一个结点
- 每一次都判断 f a s t fast fast -> n e x t next next 和 f a s t fast fast 是否为 n u l l null null 值，如果判断是的话，则说明判断的链表是无环链表。
- 当 f a s t fast fast 指针和 s l o w slow slow 指针相等的时候，则说明他们两个指针指向同一个结点，则说明有环、
- 将 f a s t fast fast 指针指向首结点，把步长速度从 2 2 2 调整为 1 1 1 并且让 f a s t fast fast 指针和 s l o w slow slow 指针同时往后移动
- 等到他们再次相遇的时候，他们所指向的结点一定是入环口
代码如下：
/**
1. Definition for singly-linked list.
2. struct ListNode {
3. int val;
4. struct ListNode *next;
5. };
*/
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* fast = head;
struct ListNode* slow = head;//让fast和slow都指向首结点
while(1)//循环操作
{
if(fast == NULL || fast->next == NULL)
return NULL;//当fast或者是fast->next指向空时，说明不是环形链表
fast = fast->next->next;//fast的步长为2
slow = slow->next;//slow的步长为1
if(fast == slow)
break;//当fast和slow相遇的时候，则不用继续往下走了，跳出while循环
}
fast = head;//把fast回到起点，slow在首次相遇点
while(fast!=slow)//当fast和slow没有相遇的时候，以相同速度往前走
{
fast = fast->next;
slow = slow->next;//步长都为1
}
return fast;//return slow也可以，因为他们相遇了
}
总结
- 如何判断有环和无环要清晰
- 算法问题要学会抽象化为数学问题求解