#P4104. 环形链表Ⅱ
-
ID: 2341
Tried: 613
Accepted: 114
Difficulty: 5
环形链表Ⅱ
题目描述
给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
如果链表中存在某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，输入数据中使用整数 pos 来表示链表尾部连接的索引（索引从 0 开始）。如果 pos 为 -1，则表示该链表中没有环。
注意：pos 不作为参数进行传递，仅用于描述链表的实际情况，输入数据仅提供链表的结构。
不允许修改链表。
输入描述
- 第一行输入一个整数
n（0≤n≤104），表示链表的节点数。 - 第二行输入
n个整数，表示链表节点的值（按顺序存储）。 - 第三行输入一个整数
pos（−1≤pos<n），表示链表尾部连接的索引，-1代表无环。
如果 n == 0，则链表为空，此时 pos 必定为 -1，且不输入第二行数据。
输出描述
- 如果链表有环，返回环的起始节点的索引（从
0开始）。 - 如果链表无环，返回
"null"。
样例1
输入
4
3 2 0 -4
1
输出
1
说明
链表中有一个环，其尾部连接到索引 1 的节点（值 2）。
样例2
输入
2
1 2
0
输出
0
说明
链表中有一个环，其尾部连接到索引 0 的节点（值 1）。
样例3
输入
1
1
-1
输出
null
说明
链表中没有环。
提示
- 链表的节点值范围：−105≤Node.val≤105。
pos仅用于构造链表，实际链表中不包含pos信息。pos = -1表示链表无环。
解题思路
本题要求在 不修改链表 的前提下，找到链表入环的第一个节点（如果有环），否则返回 null。
可以使用 快慢指针（Floyd 判圈算法） 来解决这个问题：
解法：快慢指针（Floyd 判圈算法）
-
第一阶段：判断链表是否有环
- 设定 慢指针
slow和 快指针fast，都从head出发：slow每次走一步 (slow = slow.next)。fast每次走两步 (fast = fast.next.next)。
- 如果
fast追上slow，说明有环。 - 如果
fast或fast.next为空，说明无环，返回null。
- 设定 慢指针
-
第二阶段：找到入环的第一个节点
- 让
slow重新指向head，fast仍停留在相遇点。 - 两个指针 每次都走一步 (
slow = slow.next,fast = fast.next)。 - 当
slow == fast时，相遇点就是环的入口。
- 让
为什么这样做？
- 设
head到 环入口 的距离为a，环内相遇点到入口的距离为c，环的长度为b。 - 当
slow和fast相遇时，fast比slow多走了整环的整数倍：2(a + c) = a + c + k * b (k 为整数) => a + c = k * b => a = k * b - c slow重新回到head，同时fast从相遇点开始，每次走一步：slow走a步到达入口fast也走a步到达入口- 两者相遇，入口就是入环点！
代码实现
Python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def detectCycle(head):
""" 使用快慢指针找出链表环的起点 """
slow, fast = head # 初始化快慢指针
# 第一阶段：判断是否有环
while fast and fast.next:
slow = slow.next # 慢指针走一步
fast = fast.next.next # 快指针走两步
if slow == fast: # 相遇，说明有环
break
else:
return None # 没有环，返回 null
# 第二阶段：找到环的入口
slow = head # 重新指向头部
while slow != fast: # 直到相遇
slow = slow.next
fast = fast.next
return slow # 返回入环点
if __name__ == "__main__":
import sys
input_data = sys.stdin.read().strip().split()
if not input_data:
sys.exit(0)
n = int(input_data[0])
if n == 0:
print("null")
sys.exit(0)
values = list(map(int, input_data[1:n+1]))
pos = int(input_data[n+1])
# 手动构造链表
nodes = [ListNode(val) for val in values]
for i in range(n - 1):
nodes[i].next = nodes[i+1]
if pos != -1:
nodes[-1].next = nodes[pos]
head = nodes[0]
# 调用函数查找环入口
entry = detectCycle(head)
if not entry:
print("null")
else:
# 找到环入口对应的索引
idx = 0
node = head
while node != entry:
node = node.next
idx += 1
print(idx)
C++
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
// 第一阶段：判断是否有环
while (fast && fast->next) {
slow = slow->next; // 慢指针走一步
fast = fast->next->next; // 快指针走两步
if (slow == fast) break; // 相遇，说明有环
}
if (!fast || !fast->next) return NULL; // 无环
// 第二阶段：找到环的入口
slow = head; // 重新指向头部
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow; // 返回入环点
}
int main() {
int n;
cin >> n;
if(n == 0) {
cout << "null" << endl;
return 0;
}
vector<int> vals(n);
for (int i = 0; i < n; i++) {
cin >> vals[i];
}
int pos;
cin >> pos;
// 构造链表
vector<ListNode*> nodes;
for (int i = 0; i < n; i++) {
nodes.push_back(new ListNode(vals[i]));
}
for (int i = 0; i < n - 1; i++) {
nodes[i]->next = nodes[i+1];
}
if (pos != -1) {
nodes[n-1]->next = nodes[pos];
}
ListNode* head = nodes[0];
// 查找环入口
ListNode* entry = detectCycle(head);
if (entry == nullptr) {
cout << "null" << endl;
} else {
int idx = 0;
ListNode* cur = head;
while (cur != entry) {
cur = cur->next;
idx++;
}
cout << idx << endl;
}
return 0;
}
Java
import java.util.Scanner;
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class Main {
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
// 第一阶段：判断是否有环
while (fast != null && fast.next != null) {
slow = slow.next; // 慢指针走一步
fast = fast.next.next; // 快指针走两步
if (slow == fast) break; // 相遇，说明有环
}
if (fast == null || fast.next == null) return null; // 无环
// 第二阶段：找到环的入口
slow = head; // 重新指向头部
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow; // 返回入环点
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
if(n == 0) {
System.out.println("null");
return;
}
// 读取链表节点的值
int[] values = new int[n];
for (int i = 0; i < n; i++) {
values[i] = sc.nextInt();
}
// 读取 pos 值
int pos = sc.nextInt();
// 构造链表
ListNode[] nodes = new ListNode[n];
for (int i = 0; i < n; i++) {
nodes[i] = new ListNode(values[i]);
}
for (int i = 0; i < n - 1; i++) {
nodes[i].next = nodes[i+1];
}
if (pos != -1) {
nodes[n - 1].next = nodes[pos];
}
ListNode head = nodes[0];
Solution solution = new Solution();
ListNode entry = solution.detectCycle(head);
// 如果无环则输出 "null"，否则输出环入口的索引
if (entry == null) {
System.out.println("null");
} else {
int idx = 0;
ListNode cur = head;
while (cur != entry) {
cur = cur.next;
idx++;
}
System.out.println(idx);
}
}
}