复制带随机指针的链表

只复制 next 会漏掉 random；先连 random 又找不到新节点。

第一遍给每个旧节点创建新节点并记映射，第二遍补 next 和 random。

原链表带 random · 要连 random 一起拷：每个节点除了 next，还有一根 random 随机指针。深拷贝要把 next 和 random 都复制对，难点在 random 可能指向还没创建的节点。

第一遍 · 复制出 7′ 存进 map：第一遍只做一件事：cur 走到 7，新建一个值为 7 的拷贝 7′，在 map 里记下 7→7′。先不接任何箭头。

第一遍走完 · 4 个拷贝都建好：cur 一路走到底，每个原节点都映射出一个孤立的拷贝（只有值、还没箭头）。map 现在能用原节点查到对应拷贝——这是第二遍接线的关键。

第二遍 · 用 map 把 next 接上：第二遍 cur 重新从头走：拷贝的 next 用 map 接——原 7 的 next 是 13，所以 7′.next = map[13] = 13′。一路把拷贝链的 next 全接好。

第二遍 · random 也用 map 接 · 深拷贝完成：random 同理：原 13 的 random 指向 7，于是 13′.random = map[7] = 7′。next 和 random 都用 map 翻译完，深拷贝完成，返回 map[head]=7′。

一句话记住：第一遍给每个旧节点创建新节点并记映射，第二遍补 next 和 random。

边界三连：边界三连先过：空输入、单元素、重复或相等值。能过这三类，主逻辑才算站稳。

雷区 · 为什么不能一遍边建边接：雷区：若想第一遍就接 7′.next = map[13]，但此刻 13′ 还没建，map[13] 是空的→接到 null。所以必须先全建完（第一遍）、再统一接线（第二遍）。

面试追问 1：第一遍给每个旧节点创建新节点并记映射，第二遍补 next 和 random。

面试追问 2：面试追复杂度时，不要只报 O，要把“每个元素进出几次”讲清楚。

面试追问 3：复制带随机指针的链表 不是孤题，它练的是 链表 的状态设计。

这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=linkedlist 连刷同类题；卡住时用 AI 答疑问“我的状态定义哪里不稳”。