LeetCode 142. Linked List Cycle II (Medium)

给定一个链表,返回链表中环的开始节点,若没有环,返回null

原始问题

https://leetcode.com/problems/linked-list-cycle-ii/

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

解题思路

类似LeetCode 141的解法,只是之后还要求出环开始的节点,这依赖于一些数学关系,下面来简要推导一下。

如图所示,假设slow指针运动到$Y$节点时,fast指针位于环中任意位置(图中未标出),其距$Y$点的距离为$m$。首先证明当slow指针与fast指针相遇于环中某一点$Z$时,slow指针移动距离$b$小于环的长度$L$,且fast指针只会比slow指针多移动一圈。

假设此时slow指针移动距离为$b$($b$ < $L$),fast指针比slow指针多移动了$N$圈,则:
$$b=m+2b-NL$$
$$\Rightarrow b=NL-m$$
$$\because 0 \leqslant b \leqslant L, 0 \leqslant m \leqslant L$$
$$\therefore N = 1$$
$$\Rightarrow b=L-m$$
对任意$m$及$L$,均可由上式确定唯一的$b$,故原命题成立。

下面在此基础上推导$a$与$c$之间的关系,应用上面得出的结论,两指针相遇时有:

$$2(a+b)=a+b+KL$$
式中$K$表示相遇时fast指针在环中运行的圈数。
$$\Rightarrow a=KL-b$$
$$\Rightarrow a=(K-1)L+L-b$$
$$\Rightarrow a=(K-1)L+c$$

上式意味着,若slowfast指针相遇于$Z$点后,slow指针继续前进,同时增加一个指针p从$X$点出发,则slowp的相遇点必定是$Y$,这也就是需要返回的节点。根据上述思路即可写出代码。

AC代码

C语言

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
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode * slow, * fast, * p;

if (head == NULL) {
return NULL;
}

slow = head;
fast = head;
p = head;

while (fast->next != NULL && fast->next->next != NULL) {
slow = slow->next;
fast = fast->next->next;

if (slow == fast) {
while (p != slow) {
p = p->next;
slow = slow->next;
}
return p;
}
}

return NULL;
}

相关题目

LeetCode 141. Linked List Cycle (Easy)
LeetCode 160. Intersection of Two Linked Lists (Easy)

文章目录
  1. 1. 原始问题
  2. 2. 解题思路
  3. 3. AC代码
    1. 3.1. C语言
  4. 4. 相关题目
|