复制带随机指针的复杂链表(剑指 Offer 35)
哪些公司问过
答案要点
- 难点:复制节点时 random 指向的节点可能尚未创建
- 哈希表法:两遍遍历,建立原节点到新节点的映射,时间空间 O(n)
- 原地法:每个原节点后插入复制节点,形成交错链表
- 复制节点 random = 原节点 random 的 next,需对空 random 判空
- 最后拆分两条链表并还原原链表,空间 O(1)
易错点
- 浅拷贝 random,新链表的 random 指回原链表节点
- 原地法中未判断 random 为空直接取 next
- 拆分后没有恢复原链表,修改了输入数据
面试官常见追问
- 原地法为什么不能把设置 random 和拆分放在同一遍?
- 能用递归加哈希表做吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 链表的几种经典操作247 场
- 判断链表是否有环70 场
- 合并 K 个有序链表45 场
- Y 型链表找第一个相交节点21 场
- 链表反转及其变形20 场
- 链表重排(找中点、反转、合并)20 场
- K 个一组翻转链表17 场
- 删除链表的倒数第 N 个节点15 场
- 链表排序:归并排序与快速排序9 场
- 链表每两个节点翻转8 场