环形链表 II （ LeetCode 142 ）
题目描述
给定一个链表，返回链表开始入环的第一个节点。
如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
如果 pos 是 -1，则在该链表中没有环。
注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
吴师兄的思路
1、通过快慢指针的方式，在环中寻找它们的第一次相遇的节点位置
2、当快慢指针相遇的时候：
- x 代表从头节点到环形入口节点的节点数（不包含头节点）
- y 代表从环形入口到第一次相遇节点的节点数（不包含环形入口节点）
- z 代表从第一次相遇节点到环形入口的节点数（不包含第一次相遇节点）
此时，快指针走了 x + y + n (y + z)，其中，x + y 表示快指针第一次到达相遇节点，n 代表快指针在环里面绕了多少圈。
而慢指针走了 x + y 步。
那么就出现了一个等式 x + y = [x + y + n (y + z)] / 2，即x = n（y + z）- y。
n（y + z）- y 代表的含义是一个指针从相遇节点开始出发，走了 n 圈之后回到原来的出发位置，往后退 y 步。
由于 x 代表从头节点到环形入口节点的节点数，并且x = n（y + z）- y，所以n（y + z）- y 代表的含义就是一个指针从相遇节点开始出发，走了 n 圈之后回到原来的出发位置，往后退 y 步来到了环的入口位置。
那么，我们就可以设置两个指针，一个从链表的头节点开始出发，一个指针从相遇节点开始出发，当它们相遇的时候，代表着环的入口节点找到了。
吴师兄的参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 环形链表 II （ LeetCode 142 ） : https://leetcode-cn.com/problems/linked-list-cycle-ii
public class Solution {
public ListNode detectCycle(ListNode head) {
// 1、通过快慢指针的方式，在环中寻找它们的第一次相遇的节点位置
// 2、定义一个慢指针，每次只会向前移动 1 步
ListNode slow = head;
// 3、定义一个快指针，每次只会向前移动 2 步
ListNode fast = head;
// 4、如果链表有环，那么无论怎么移动，fast 指向的节点都是有值的
while (fast != null && fast.next != null) {
// 慢指针每次只会向前移动 1 步
slow = slow.next;
// 快指针每次只会向前移动 2 步
fast = fast.next.next;
// 快慢指针相遇，说明有环
// x 代表从头节点到环形入口节点的节点数（不包含头节点）
// y 代表从环形入口到第一次相遇节点的节点数（不包含环形入口节点）
// z 代表从第一次相遇节点到环形入口的节点数（不包含第一次相遇节点）
// y + z 代表环的节点总数
// 此时，快指针走了 x + y + n (y + z)
// 其中，x + y 表示快指针第一次到达相遇节点，n 代表快指针在环里面绕了多少圈
// 此时，慢指针走了 x + y 步
// 由于快指针每次走 2 步，所以快慢指针第一次相遇的时候出现一个等式
// x + y = [x + y + n (y + z)] / 2
// 即 2 * (x + y) = x + y + n (y + z)
// 即 x + y = n（y + z）
// 即 x = n（y + z）- y
// 我们的目的就是去求 x
// 定义两个指针，一个指向相遇节点，定义为 b，一个指向链表头节点，定义为 a
// b 在环中绕圈圈，走了 n（y + z）步会回到原处，即回到相遇节点处
// 由于 y 代表从环形入口到第一次相遇节点的节点数（不包含环形入口节点）
// 所以 n（y + z） - y 时，b 到达了环形入口节点位置
// 由于 x 代表从头节点到环形入口节点的节点数（不包含头节点）
// 所以 a 走了 x 步时，a 到达了环形入口节点位置
// 当 x = n（y + z）- y 时，找到了环形入口节点位置
// 5、开始寻找环入口
if (slow == fast) {
// 定义两个指针，一个指向相遇节点，定义为 b，一个指向链表头节点，定义为 a
// 一个指向相遇节点，定义为 b
ListNode b = fast;
// 一个指向链表头节点，定义为 a
ListNode a = head;
// 让 a 、b 两个指针向前移动，每次移动一步，直到相遇位置
// 由于有环，必然相遇
// 当 b 走了 n（y + z） - y 时，b 到达了环形入口节点位置
// 当 a 走了 x 步时，a 到达了环形入口节点位置
// a 与 b 相遇
while (a != b) {
// a 指针每次只会向前移动 1 步
a = a.next;
// b 指针每次只会向前移动 1 步
b = b.next;
}
// 6、返回 a 和 b 相遇的节点位置就是环形入口节点位置
return a;
}
}
// 没有环，返回 null
return null;
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 环形链表 II （ LeetCode 142 ） : https://leetcode-cn.com/problems/linked-list-cycle-ii
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
// 1、通过快慢指针的方式，在环中寻找它们的第一次相遇的节点位置
// 2、定义一个慢指针，每次只会向前移动 1 步
ListNode *slow = head;
// 3、定义一个快指针，每次只会向前移动 2 步
ListNode *fast = head;
// 4、如果链表有环，那么无论怎么移动，fast 指向的节点都是有值的
while (fast != NULL && fast->next != NULL) {
// 慢指针每次只会向前移动 1 步
slow = slow->next;
// 快指针每次只会向前移动 2 步
fast = fast->next->next;
// 快慢指针相遇，说明有环
// x 代表从头节点到环形入口节点的节点数（不包含头节点）
// y 代表从环形入口到第一次相遇节点的节点数（不包含环形入口节点）
// z 代表从第一次相遇节点到环形入口的节点数（不包含第一次相遇节点）
// y + z 代表环的节点总数
// 此时，快指针走了 x + y + n (y + z)
// 其中，x + y 表示快指针第一次到达相遇节点，n 代表快指针在环里面绕了多少圈
// 此时，慢指针走了 x + y 步
// 由于快指针每次走 2 步，所以快慢指针第一次相遇的时候出现一个等式
// x + y = [x + y + n (y + z)] / 2
// 即 2 * (x + y) = x + y + n (y + z)
// 即 x + y = n（y + z）
// 即 x = n（y + z）- y
// 我们的目的就是去求 x
// 定义两个指针，一个指向相遇节点，定义为 b，一个指向链表头节点，定义为 a
// b 在环中绕圈圈，走了 n（y + z）步会回到原处，即回到相遇节点处
// 由于 y 代表从环形入口到第一次相遇节点的节点数（不包含环形入口节点）
// 所以 n（y + z） - y 时，b 到达了环形入口节点位置
// 由于 x 代表从头节点到环形入口节点的节点数（不包含头节点）
// 所以 a 走了 x 步时，a 到达了环形入口节点位置
// 当 x = n（y + z）- y 时，找到了环形入口节点位置
// 5、开始寻找环入口
if (slow == fast) {
// 定义两个指针，一个指向相遇节点，定义为 b，一个指向链表头节点，定义为 a
// 一个指向相遇节点，定义为 b
ListNode *b = fast;
// 一个指向链表头节点，定义为 a
ListNode *a = head;
// 让 a 、b 两个指针向前移动，每次移动一步，直到相遇位置
// 由于有环，必然相遇
// 当 b 走了 n（y + z） - y 时，b 到达了环形入口节点位置
// 当 a 走了 x 步时，a 到达了环形入口节点位置
// a 与 b 相遇
while (a != b) {
// a 指针每次只会向前移动 1 步
a = a->next;
// b 指针每次只会向前移动 1 步
b = b->next;
}
// 6、返回 a 和 b 相遇的节点位置就是环形入口节点位置
return a;
}
}
// 没有环，返回 NULL
return NULL;
}
};
3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 环形链表 II （ LeetCode 142 ） : https://leetcode-cn.com/problems/linked-list-cycle-ii
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
# 1、通过快慢指针的方式，在环中寻找它们的第一次相遇的节点位置
# 2、定义一个慢指针，每次只会向前移动 1 步
slow = head
# 3、定义一个快指针，每次只会向前移动 2 步
fast = head
# 4、如果链表有环，那么无论怎么移动，fast 指向的节点都是有值的
while fast != None and fast.next != None :
# 慢指针每次只会向前移动 1 步
slow = slow.next
# 快指针每次只会向前移动 2 步
fast = fast.next.next
# 快慢指针相遇，说明有环
# x 代表从头节点到环形入口节点的节点数（不包含头节点）
# y 代表从环形入口到第一次相遇节点的节点数（不包含环形入口节点）
# z 代表从第一次相遇节点到环形入口的节点数（不包含第一次相遇节点）
# y + z 代表环的节点总数
# 此时，快指针走了 x + y + n y + z)
# 其中，x + y 表示快指针第一次到达相遇节点，n 代表快指针在环里面绕了多少圈
# 此时，慢指针走了 x + y 步
# 由于快指针每次走 2 步，所以快慢指针第一次相遇的时候出现一个等式
# x + y = [x + y + n y + z)] / 2
# 即 2 * x + y) = x + y + n y + z)
# 即 x + y = n（y + z）
# 即 x = n（y + z）- y
# 我们的目的就是去求 x
# 定义两个指针，一个指向相遇节点，定义为 b，一个指向链表头节点，定义为 a
# b 在环中绕圈圈，走了 n（y + z）步会回到原处，即回到相遇节点处
# 由于 y 代表从环形入口到第一次相遇节点的节点数（不包含环形入口节点）
# 所以 n（y + z） - y 时，b 到达了环形入口节点位置
# 由于 x 代表从头节点到环形入口节点的节点数（不包含头节点）
# 所以 a 走了 x 步时，a 到达了环形入口节点位置
# 当 x = n（y + z）- y 时，找到了环形入口节点位置
# 5、开始寻找环入口
if slow == fast :
# 定义两个指针，一个指向相遇节点，定义为 b，一个指向链表头节点，定义为 a
# 一个指向相遇节点，定义为 b
b = fast
# 一个指向链表头节点，定义为 a
a = head
# 让 a 、b 两个指针向前移动，每次移动一步，直到相遇位置
# 由于有环，必然相遇
# 当 b 走了 n（y + z） - y 时，b 到达了环形入口节点位置
# 当 a 走了 x 步时，a 到达了环形入口节点位置
# a 与 b 相遇
while a != b :
# a 指针每次只会向前移动 1 步
a = a.next
# b 指针每次只会向前移动 1 步
b = b.next
# 6、返回 a 和 b 相遇的节点位置就是环形入口节点位置
return a
# 没有环，返回 None
return None
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-12-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
