如何复制带 random 指针的复杂链表?
哪些公司问过
答案要点
- 关键是建立原节点到新节点的映射,解决 random 指向尚未复制节点的问题
- 哈希表法:先建全部新节点,再按映射设置 next 和 random,时间空间 O(n)
- 原地法:交错插入拷贝节点,拷贝的 random 等于原 random 的 next,最后拆分
- random 为空时要单独处理,拆分时要恢复原链表
- 本质是深拷贝中重建对象间引用,浅拷贝会让新旧对象共享被引用对象
易错点
- 新节点的 random 直接指向原链表节点
- 拆分后没有恢复原链表
- 忽略 random 为空的情况导致空指针访问
面试官常见追问
- 这道题和游戏里复制对象有什么关系?
- 原地法拆分时要注意什么?
- 如果是复制一个有环的图结构呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 链表的几种经典操作247 场
- 判断链表是否有环70 场
- 合并 K 个有序链表45 场
- Y 型链表找第一个相交节点21 场
- 链表反转及其变形20 场
- 链表重排(找中点、反转、合并)20 场
- K 个一组翻转链表17 场
- 删除链表的倒数第 N 个节点15 场
- 链表排序:归并排序与快速排序9 场
- 链表每两个节点翻转8 场