复制带随机指针的链表

记住这一招：先复制全部、再用 map 取副本连线。

这是原链表：上方一排是原节点，灰线是它的 next 与 random 指针。右侧 map 现在还是空的，我们要逐个建出副本。

阶段①复制：来到节点 7，新建一个值相同的副本 7'（此时副本的 next/random 都先留空），准备写入 map。

写入 map[7] = 7'。副本已登记，右侧 map 多了一条「7 → 7'」。

阶段①复制：来到节点 13，新建一个值相同的副本 13'（此时副本的 next/random 都先留空），准备写入 map。

写入 map[13] = 13'。副本已登记，右侧 map 多了一条「13 → 13'」。

阶段①复制：来到节点 11，新建一个值相同的副本 11'（此时副本的 next/random 都先留空），准备写入 map。

写入 map[11] = 11'。副本已登记，右侧 map 多了一条「11 → 11'」。

阶段①复制：来到节点 10，新建一个值相同的副本 10'（此时副本的 next/random 都先留空），准备写入 map。

写入 map[10] = 10'。副本已登记，右侧 map 多了一条「10 → 10'」。

阶段②连 next：看原图，7 的 next 指向 13（高亮这条边）。

用 map 取副本：7'.next = map[13] = 13'。副本之间的 next 接上了。

阶段②连 next：看原图，13 的 next 指向 11（高亮这条边）。

用 map 取副本：13'.next = map[11] = 11'。副本之间的 next 接上了。

阶段②连 next：看原图，11 的 next 指向 10（高亮这条边）。

用 map 取副本：11'.next = map[10] = 10'。副本之间的 next 接上了。

阶段②连 next：节点 10 是尾节点，原 next 为 null，于是副本 10'.next 也置 null。next 链全部连完。

阶段③连 random：节点 7 的 random 为 null，副本 7'.random 也置 null。

阶段③连 random：原图里 13 的 random 指向 7（高亮这条 random 边）。

用 map 取副本：13'.random = map[7] = 7'。哪怕 random 指向链表中间，也能精准接上——这正是先建 map 的好处。

阶段③连 random：原图里 11 的 random 指向 7（高亮这条 random 边）。

用 map 取副本：11'.random = map[7] = 7'。哪怕 random 指向链表中间，也能精准接上——这正是先建 map 的好处。

阶段③连 random：原图里 10 的 random 指向 13（高亮这条 random 边）。

用 map 取副本：10'.random = map[13] = 13'。哪怕 random 指向链表中间，也能精准接上——这正是先建 map 的好处。

全部节点都已复制、next 与 random 都按原图连上了。返回 map[头节点] = 7' 这个副本头，就是整条链表的深拷贝。

边界先想清。

两个高频追问。