随机链表复制：先建旧→新，再翻译指针
next 和 random 都是「指向某个节点」。复制关系之前，必须先能从旧节点找到它的新副本。
两遍扫描：第一遍按 next 走原链，为每个旧节点 new 一颗同值新节点，写入哈希 旧→新；第二遍再走一遍，新.next = 映射[旧.next]，新.random = 映射[旧.random]，nil 在 map 里取到的也是 nil。返回映射[head]。时间 O(n)，空间 O(n)。原地织线可把额外空间降到 O(1)。
这是 LeetCode 138. Copy List with Random Pointer。链表每个节点除了 Next，还有一根 Random，可以指向任意节点或空。要深拷贝整条链：新链的值相同，Next 和 Random 都指向新链里对应的那一颗，不能指回原链。
主例节点值 7→13→11→10→1。Random 分别是空、7、1、11、7，也就是下标映射 [−1, 0, 4, 2, 0]。复制完成后，新链里 13 的 Random 必须指向新的 7，而不是原来的 7。
只顺着 Next 建新节点，会在 Random 指向前方或后方时卡住：对方的新副本可能还没 new 出来，或者你手里只有旧指针。缺的是一张「旧节点到新节点」的对照表。本文先建全表，再统一接线；也可以把副本织在原节点后面，用位置代替哈希。
第一遍：建旧→新映射
第一直觉是走原链，边走边 new，同时接 Next 和 Random。Next 还好说，它总指向「下一个」，可以下一轮再补。Random 可以指向还没走到的节点，也可以指回已经走过但当时没记下副本的节点。主例 13 的 Random 指回 7，11 的 Random 指向末尾的 1——单次扫描无法保证对方已存在。
所以第一遍只做一件事：按 Next 顺序遍历，为每个旧节点创建一个只填了 Val 的新节点，写入 mp[旧] = 新。新节点此刻是孤立的，Next 和 Random 都还是 nil。演示停在已经建好 7、13、11 三颗副本的时刻，后面的 10、1 同样处理。
空链表直接返回空。哈希表在 Go 里对 nil 键取值得到零值 nil，第二遍不必给空指针写特判。
两遍扫描先保证每一个旧节点都有新副本，再谈指向谁。Random 指向前方时，副本已经在表里；指向空时，map[nil] 就是 nil。
第二遍：连 next 与 random
表齐了，再从头走旧链。对每个旧节点 cur：新副本是 mp[cur]，它的 Next 写成 mp[cur.Next]，Random 写成 mp[cur.Random]。翻译一次，指向就从旧世界换到新世界。
主例第二帧停在 13：旧 13 的 Next 是 11，Random 是 7，新 13 接到新 11、新 7。7 的 Random 是空，新 7 的 Random 保持 nil。11 接到新 10，Random 接到新 1。走完返回 mp[head]，也就是新的 7。演示最后一帧全部完成。
不想用哈希时，把新节点织在旧节点后面：7→7'→13→13'→…。第二趟用 cur.Random.Next 找到对方的副本（副本就在旧节点后面），第三趟把织在一起的链拆开。额外空间 O(1)，三次遍历，和哈希两遍是同一张对照表，只是对照关系改用位置表示。
Go：哈希映射两遍扫描
func copyRandomList(head *Node) *Node {if head == nil { return nil }mp := map[*Node]*Node{}for cur := head; cur != nil; cur = cur.Next {mp[cur] = &Node{Val: cur.Val}}for cur := head; cur != nil; cur = cur.Next {mp[cur].Next = mp[cur.Next]mp[cur].Random = mp[cur.Random]}return mp[head]}
1空链直接返回。后面的 map 对 nil 取值也是 nil，但没有头就没有 mp[head]。
2第一遍只复制 Val。主例五颗旧节点对应五颗孤立新节点。
3第二遍翻译指针。mp[cur.Next]、mp[cur.Random] 在对方是 nil 时得到 nil，7 的 Random 不用另写 if。
4返回 mp[head]。调用方拿到的是新 7，从它出发走 Next / Random 都不会回到旧链。
总结
先建旧→新，再把 next/random 翻译过去。主例 13 的 random 必须指向新的 7。
- 单次边建边接会在 Random 指向未创建节点时失败。主例 11 指向末尾的 1。
- map[nil] 得 nil，空指针不必特判。
- 织线是同一张对照表：副本紧跟旧节点，用位置代替哈希，额外空间 O(1)。