#P4043. 环形链表
-
ID: 2285
Tried: 84
Accepted: 25
Difficulty: 5
环形链表
题目描述
给定一个 单链表，其输入格式为 (地址, 值, 下一个地址) 的三元组，判断链表是否存在 环。
- 如果存在环，返回
true。 - 如果不存在环，返回
false。
输入格式
-
第一行输入一个整数
n，表示链表的 节点数。（0 ≤ n ≤ 10⁴） -
接下来的
n行，每行包含 三个整数：addr：当前节点的 地址（唯一标识）。val：当前节点的 值（-10⁵ ≤ val ≤ 10⁵）。next_addr：当前节点的 下一个节点地址：- 若
next_addr = -1，表示链表结束。 - 若
next_addr指向某个addr，表示连接到该地址，可能形成 环。
- 若
-
特别规定：
- 第一行的
addr永远是head（链表头）。 - 其余节点的顺序可以是 任意顺序，需要 按照
next_addr构建链表。
- 第一行的
输出格式
- 输出
true或false，表示链表是否存在环。
样例 1
输入
4
100 3 200
200 2 300
300 0 400
400 -4 200
输出
true
说明：
- 链表结构：
100 -> 200 -> 300 -> 400 ^ | |_________| - 尾节点
400连接到200形成环。
样例 2
输入
2
100 1 200
200 2 -1
输出
false
说明：
- 链表结构：
100 -> 200 -> NULL - 无环，返回
false。
样例 3
输入
1
100 1 -1
输出
false
说明：
- 单个节点，无环，返回
false。
解题思路
1. 使用哈希表构建链表
- 由于输入顺序可能 无序，需 先存储所有节点。
- 用 哈希表
nodes存储{addr: (val, next_addr)}。 - 找到 头节点
head_addr（输入第一行的addr）。 - 按照
next_addr顺序重建链表。
2. 使用快慢指针判断环
- 慢指针
slow：每次移动1步。 - 快指针
fast：每次移动2步。 - 如果
fast追上slow，说明有环，返回true。 - 如果
fast遇到NULL，说明无环，返回false。
时间复杂度： ( O(n) )
空间复杂度： ( O(n) )（哈希表存储所有地址）
代码实现
C++ 版本
#include <iostream>
#include <unordered_map>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 封装链表构建：根据存储的节点数据构建链表（注意：节点的输入顺序可能无序）
ListNode* buildLinkedList(unordered_map<int, pair<int, int>> &nodes, int head_addr) {
unordered_map<int, ListNode*> addressMap; // 用于保存已创建的节点
// 创建头节点
ListNode *head = new ListNode(nodes[head_addr].first);
addressMap[head_addr] = head;
int curr_addr = nodes[head_addr].second;
ListNode *prev = head;
while (curr_addr != -1) {
// 如果当前地址已创建，说明环出现，直接链接即可
if (addressMap.find(curr_addr) != addressMap.end()) {
prev->next = addressMap[curr_addr];
break;
}
// 创建新节点
ListNode *newNode = new ListNode(nodes[curr_addr].first);
addressMap[curr_addr] = newNode;
prev->next = newNode;
prev = newNode;
curr_addr = nodes[curr_addr].second;
}
return head;
}
// 使用快慢指针判断链表是否有环
bool hasCycle(ListNode *head) {
if (!head || !head->next) return false;
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
int main(){
int n;
cin >> n;
if(n == 0){
cout << "false" << endl;
return 0;
}
// 用于存储节点数据： {addr : (val, next_addr)}
unordered_map<int, pair<int, int>> nodes;
int head_addr, val, next_addr;
// 读取第一行（头节点）
cin >> head_addr >> val >> next_addr;
nodes[head_addr] = {val, next_addr};
// 读取剩余 n-1 行
for (int i = 1; i < n; i++){
int addr;
cin >> addr >> val >> next_addr;
nodes[addr] = {val, next_addr};
}
// 构建链表（按照 next_addr 链接）
ListNode* head = buildLinkedList(nodes, head_addr);
cout << (hasCycle(head) ? "true" : "false") << endl;
return 0;
}
Python 版本
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 判断链表是否有环（快慢指针）
def has_cycle(head):
if not head or not head.next:
return False
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
if __name__ == "__main__":
n = int(input().strip())
if n == 0:
print("false")
exit()
nodes = {}
head_addr, val, next_addr = map(int, input().split())
nodes[head_addr] = (val, next_addr)
for _ in range(n - 1):
addr, val, next_addr = map(int, input().split())
nodes[addr] = (val, next_addr)
# 构建链表
address_map = {}
head = ListNode(nodes[head_addr][0])
address_map[head_addr] = head
curr_addr = nodes[head_addr][1]
prev = head
while curr_addr != -1:
if curr_addr in address_map: # 形成环
prev.next = address_map[curr_addr]
break
new_node = ListNode(nodes[curr_addr][0])
address_map[curr_addr] = new_node
prev.next = new_node
prev = new_node
curr_addr = nodes[curr_addr][1]
print("true" if has_cycle(head) else "false")
Java解法
import java.util.HashMap;
import java.util.Scanner;
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class Main {
// 构建链表：根据 nodes（addr -> [val, next_addr]）和头地址构建链表
public static ListNode buildLinkedList(HashMap<Integer, int[]> nodes, int headAddr) {
HashMap<Integer, ListNode> addressMap = new HashMap<>();
ListNode head = new ListNode(nodes.get(headAddr)[0]);
addressMap.put(headAddr, head);
int currAddr = nodes.get(headAddr)[1];
ListNode prev = head;
while (currAddr != -1) {
if (addressMap.containsKey(currAddr)) { // 已创建，说明形成环
prev.next = addressMap.get(currAddr);
break;
}
ListNode newNode = new ListNode(nodes.get(currAddr)[0]);
addressMap.put(currAddr, newNode);
prev.next = newNode;
prev = newNode;
currAddr = nodes.get(currAddr)[1];
}
return head;
}
// 使用快慢指针判断链表是否存在环
public static boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
if(n == 0){
System.out.println("false");
scanner.close();
return;
}
// 存储节点数据： key 为 addr，value 为 int[]{val, next_addr}
HashMap<Integer, int[]> nodes = new HashMap<>();
// 读取头节点（第一行的三个整数）
int headAddr = scanner.nextInt();
int val = scanner.nextInt();
int nextAddr = scanner.nextInt();
nodes.put(headAddr, new int[]{val, nextAddr});
for (int i = 1; i < n; i++) {
int addr = scanner.nextInt();
val = scanner.nextInt();
nextAddr = scanner.nextInt();
nodes.put(addr, new int[]{val, nextAddr});
}
ListNode head = buildLinkedList(nodes, headAddr);
System.out.println(hasCycle(head) ? "true" : "false");
scanner.close();
}
}