LeetCode 热题 100：随机链表的深拷贝

• 原子逻辑：给定原地址 Pold，我必须能立刻找到对应的新地址 Pnew。
• 工具选择：std::unordered_map<Node*, Node*>。

思路过程：

1. 第一遍遍历：把所有新节点创建出来，并把 (原节点地址，新节点地址) 存入哈希表。
2. 第二遍遍历：根据哈希表，把新节点的 next 和 random 指针连接起来。

评价：这是最直观的逻辑，时间复杂度 O(n)，空间复杂度 O(n)。

方案二：利用'空间拓扑'消除映射 (Interweaving)

如果我们追求极致，不使用额外的哈希表（即 O(1) 空间复杂度），该怎么办？

回到第一性原理：映射的本质是建立关联。除了哈希表，还有什么方式能让原节点和新节点产生物理关联？

天才的想法：把新节点直接'嫁接'在原节点后面。

思路过程：

第一步：复制并嵌入 (Copy & Insert)

将每个新节点 A' 插入到原节点 A 和 A.next 之间。

• 原结构：A -> B -> C
• 新结构：A -> A' -> B -> B' -> C -> C' 本质：现在 A' 的位置就在 A 的旁边。这意味着 A.next 就是 A'。

第二步：复制随机指针 (Copy Random)

因为 A' 紧跟在 A 后面，那么 A.random 的拷贝（即 A'.random）一定就在 A.random.next 的位置。

• 逻辑：A->next->random = A->random->next (需注意判空)。

第三步：拆解链表 (Split)

将这个长链表拆分为原链表和新链表，恢复原貌并提取拷贝。

C++ 代码实现 (基于方案二)

这是最体现算法功底的解法。我们一步步用代码实现上述思维：

/* // 节点定义
class Node {
 public:
  int val;
  Node* next;
  Node* random;
  Node(int _val) { val = _val; next = NULL; random = NULL; }
}; */
class Solution {
 public:
  Node* copyRandomList(Node* head) {
    if (!head) return nullptr;
    // --- 第一阶段：在每个原节点后面创建一个新节点 ---
    // 原：A -> B -> C
    // 现：A -> A' -> B -> B' -> C -> C'
    Node* curr = head;
    while (curr) {
      Node* newNode = new Node(curr->val);
      newNode->next = curr->next;
      curr->next = newNode;
      curr = newNode->next;
    }
    // --- 第二阶段：设置新节点的 random 指针 ---
    // 核心逻辑：A'.random = A.random->next
    curr = head;
    while (curr) {
      if (curr->random) {
        curr->next->random = curr->random->next;
      }
      curr = curr->next->next; // 移动到下一个原节点
    }
    // --- 第三阶段：将交错的链表拆开 ---
    // 恢复原链表，提取新链表
    Node* newHead = head->next;
    curr = head;
    Node* copyCurr = newHead;
    while (curr) {
      curr->next = curr->next->next; // 恢复原链表连接
      if (copyCurr->next) {
        copyCurr->next = copyCurr->next->next; // 提取新链表连接
      }
      curr = curr->next;
      copyCurr = copyCurr->next;
    }
    return newHead;
  }
};

用第一性原理思考这道题的轨迹是：

1. 明确原子目标：创建 n 个独立节点，并复制复杂的指向关系。
2. 识别瓶颈：random 指针指向的对象在创建当前节点时可能尚未就绪，或无法通过当前指针直接定位。
3. 寻找关联媒介：
   • 方案一：使用外部内存（哈希表）作为媒介。
   • 方案二：使用内部物理位置（交错排列）作为媒介。

如果理解了'如何建立 A 与 A' 的稳定关联'，你就真正掌握了这道题的精髓。

面试回答

第一步：明确本质

'首先，这道题的本质是处理带有复杂拓扑关系的内存拷贝。普通的单链表深拷贝只需要线性遍历，但这里的 random 指针打破了线性的顺序，它可能指向之后还没创建的节点，也可能指向之前的节点。'

第二步：提出矛盾

'这里的核心矛盾在于：

当我在克隆节点 A 时，我无法立刻确定它的 random 指针应该指向哪里，因为被指向的节点 B 可能还没被创建，或者我无法在 $O(1)$ 时间内找到 B 的克隆体。'

第三步：从直觉出发

'为了打破这个瓶颈，我首先想到的是建立映射关系：

• 思路：使用一个哈希表（Hash Map），以原节点地址为 Key，新节点地址为 Value。
• 过程：第一遍遍历创建所有节点并存入 map，第二遍根据 map 连接 next 和 random。
• 评价：这个方案的时间复杂度是 O(n)，非常高效，但它需要 O(n) 的额外空间来存储哈希表。'

第四步：极致优化（空间换位置）

'如果面试官要求空间复杂度优化到 O(1)，我就需要利用原有的物理空间来存储映射关系，也就是所谓的'原地交错法'：

1. 节点嫁接：我遍历原链表，把每个克隆节点 A' 直接插入到原节点 A 的后面。这样，原节点和新节点就成对出现了。
2. 关系同步：此时，映射关系隐含在位置中。如果 A.random 指向 B，那么 A' 的 random 就应该指向 B 的后继节点（即 B'）。这一步我们只需要一次遍历就能完成。
3. 链表拆分：最后，通过'跳跃式'重新连接指针，将交错的链表还原为原链表和拷贝链表。'

第五步：总结复杂度

'这种方案的精妙之处在于，它通过改变链表的物理结构，用 O(1) 的辅助空间巧妙地替代了哈希表的映射功能，同时时间复杂度依然保持在 O(n)。'

面试官可能会追问的细节：

• Q: 拆分链表（第三步）时需要注意什么？
  • A: 需要注意空指针（nullptr）的处理，尤其是当 curr->next 是最后一个节点时，要确保不要访问 nullptr->next。
• Q: 哈希表法和交错法哪个更好？
  • A: 在工程实践中，哈希表法代码更简洁、易维护，不容易出错；在对内存极其敏感的嵌入式或底层开发中，交错法（O(1) 空间）更有优势。