面试题库 › 客户端 › 如何复制带 random 指针的复杂链表?

如何复制带 random 指针的复杂链表?

难度 ★★☆在 3 场真实面经中被问到 方向:客户端考点:链表

哪些公司问过

字节跳动3

常见岗位:C++ 后端、游戏客户端、游戏服务端

答案要点

  1. 关键是建立原节点到新节点的映射,解决 random 指向尚未复制节点的问题
  2. 哈希表法:先建全部新节点,再按映射设置 next 和 random,时间空间 O(n)
  3. 原地法:交错插入拷贝节点,拷贝的 random 等于原 random 的 next,最后拆分
  4. random 为空时要单独处理,拆分时要恢复原链表
  5. 本质是深拷贝中重建对象间引用,浅拷贝会让新旧对象共享被引用对象

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题