copy · jump 指针 & 哈希表

复制带随机指针的链表

每个节点除了 next，还多一个 jump 指针，指向链表中任意一个别的节点（本题保证非空）。要做一份完全独立的拷贝：新链表的 next 与 jump 必须指向新节点，不能借用任何旧节点。难点在 jump：遍历到某个节点、想接好它的 jump 时，目标节点的副本可能还没被创建。本页给出两种解法，各配一个可单步演示的 lab:Map 两遍法——一张 $Map(旧节点 \to 新节点)$ 记录对应关系，遍历两遍，先逐个克隆登记、再回头用 Map 把每个新节点的 next 和 jump 一次接好，额外空间 O(n)；以及 交织法——把副本穿插进原链表，用物理相邻关系替代 Map，把额外空间降到 O(1)。

1 · Map 两遍法 · O(n) 空间

为什么非得用 Map?如果只遍历一遍、边克隆边接指针：接 next 没问题（后一个节点紧接着就会克隆），但接 jump 时目标可能还在后面、副本尚未存在，无法引用。Map 把「旧节点 → 它的副本」这层对应关系显式存下来，于是第二遍面对任何一个 jump 目标，无论它在前在后、是否已遍历过，都能 $O(1)$ 查到对应的新节点。本质是用 O(n) 的额外空间，换取「先建好全部节点、再统一接线」的自由。

2 · 交织法 · O(1) 额外空间

能不能不借助 Map？有一个经典技巧：把副本穿插进原链表——在每个原节点后面紧跟插入它的副本(A → A' → B → B' → …)，分三遍完成。穿插：逐个把 A' 插到 A 之后；接 jump：此时 A'.jump = A.jump.next——原节点 A.jump 的紧后一个，正是它的副本，无需查表；拆链：把交织的一条链拆成原链与副本链两条，并还原原链表。它把「旧 → 新」的对应关系编码在物理相邻位置里，从而省掉 Map。下面的 lab 把这三遍逐步画出来：副本在同一排里穿插，拆链时整排下移、再逐个「解开」成上下两条独立链。

交织法为什么成立？关键在接 jump 的那一刻——副本 A' 永远紧跟在本体 A 后面，于是「A 的 jump 目标」的副本，恰好是「A.jump 的 next」。这层「旧 → 新」映射不再需要 Map，而是物理地编码在相邻位置里，额外空间从 $O(n)$ 降到 $O(1)$ 。

两处最容易写错。其一，接 jump 必须判空：A.jump 可能为 null（本题保证非空，但通用写法仍要写 A.jump ? A.jump.next : null），否则 null.next 抛错。其二，拆链必须同时还原原链表——只挑出副本还不够，若不把 A.next 接回原来的后继，原链表就被破坏了；接 jump 与拆链也不能合并成一遍，因为拆链一旦改写 next，「副本紧跟本体」这个不变量就失效了。取舍：交织法省下 $O(n)$ 空间，代价是临时改动原链表、三遍遍历、逻辑更易错；若不在意额外空间，Map 两遍法更直接、更不易写错。