862 字
4 分钟
4月7日刷题笔记——随机链表复制和删除链表节点
本篇题目
#138随机链表的复制
Medium
#237删除链表中的节点
Medium
LeetCode 138 · 随机链表的复制
#138随机链表的复制
Medium
思路
每个节点除了 next，还有一个 random 指针，可以指向链表中任意节点（或 None）。
难点在于：连接 random 时，目标节点可能还没被创建出来。比如处理节点 A 时，想让新 A 的 random 指向新 C，但新 C 还不存在。
解决方案：分两步走，先造节点，再连线。
第一步：遍历原链表，为每个节点创建对应的新节点，存入哈希表：
dic = { 原A: 新A, 原B: 新B, 原C: 新C }此时新节点的 next 和 random 都是 None，只是先把所有节点造好。
第二步：再遍历一遍，统一连接 next 和 random。此时所有新节点都已存在，可以放心查字典：
dic[curr].next = dic.get(curr.next) # 原节点的next → 对应的新节点dic[curr].random = dic.get(curr.random) # 原节点的random → 对应的新节点为什么 key 是节点对象而不是节点值？
因为节点值可能重复（比如两个节点都是 1），用值做 key 会冲突。节点对象本身在内存中是唯一的，用对象做 key 才能精确对应。
代码
class Solution: def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]': if not head: return curr = head dic = {}
# 第一步：造节点，建立"原节点 → 新节点"的映射 while curr: dic[curr] = Node(curr.val) curr = curr.next
curr = head
# 第二步：连接 next 和 random while curr: dic[curr].next = dic.get(curr.next) # 找到原节点next对应的新节点 dic[curr].random = dic.get(curr.random) # 找到原节点random对应的新节点 curr = curr.next
return dic[head]关键细节
dic[curr].next = dic.get(curr.next) 拆解
curr.next → 原B（这是 key）dic.get(原B) → 新B（这是 value）dic[curr].next = 新B → 新curr的next指向新B为什么用 dic.get() 而不是 dic[]？
curr.next 或 curr.random 可能是 None：
dic.get(None)→ 返回None，不报错 ✅dic[None]→ 抛出KeyError❌
常见 bug
# ❌ 错误写法：把 dic[curr] 覆盖掉了，映射关系丢失dic[curr] = dic.get(curr.next)dic[curr].random = dic.get(curr.random) # 此时 dic[curr] 已经不是新节点了
# ✅ 正确写法：修改新节点的属性，不动字典本身dic[curr].next = dic.get(curr.next)dic[curr].random = dic.get(curr.random)总结
- 核心技巧：哈希表建立”原节点 → 新节点”映射，先批量造节点，再批量连线
- 复杂度：时间 O(n)，空间 O(n)
LeetCode 237 · 删除链表中的节点
#237删除链表中的节点
Medium
思路
正常删除节点需要找到前一个节点，然后：
前节点.next = 当前节点.next但这题只给你当前节点，没给 head，根本找不到前节点。
换个思路：不删自己，把下一个节点的值复制过来，再删下一个节点。
删前： ... → node(3) → next(4) → ... ↓第一步： ... → node(4) → next(4) → ... # 把值覆盖 ↓第二步： ... → node(4) → next.next → ... # 跳过next视觉上看起来 node 被删掉了，实际上是”偷梁换柱”。
代码
class Solution: def deleteNode(self, node): node.val = node.next.val # 把下一个节点的值复制到当前节点 node.next = node.next.next # 跳过下一个节点总结
- 核心技巧：无法找前驱时，用”值覆盖 + 跳过下一节点”模拟删除
- 复杂度：时间 O(1)，空间 O(1)
两题横向对比
| 题目 | 核心技巧 | 关键限制 |
|---|---|---|
| 138 随机链表的复制 | 哈希表映射，两轮遍历 | key 必须是节点对象，不能是节点值 |
| 237 删除链表中的节点 | 值覆盖 + 跳过下一节点 | 只给当前节点，无法找前驱 |
4月7日刷题笔记——随机链表复制和删除链表节点
https://www.yyylegend.com/posts/4月7日刷题笔记随机链表复制和删除链表节点/