跳到主要内容

LeetCode 138. 随机链表的复制

本节目标

用旧节点到新节点的映射，完整深拷贝 next 与 random 两类关系。

这道题将链表从单一的 next 关系扩展为对象图：每个节点还可通过 random 指向任意节点或空指针。它是数据结构综合中的链表迁移练习，也是“按对象身份建立对应关系”的基础。

查看原题

题意与约束​

返回一条与原链表值序列和两类指向关系完全一致的新链表。新节点不能复用原节点；新链表中的 next、random 都不能指回旧链表。

节点值不能替代节点身份：不同旧节点可能有相同值，却应对应不同的新节点。因此映射的键必须是旧节点对象，而不是它的 val。

第一反应​

使用两遍哈希映射。第一遍沿 next 遍历，为每个旧节点创建一个新节点，记录“旧节点 → 新节点”。第二遍再次遍历原链表，根据映射恢复每个新节点的 next 和 random。

访问 cur.next 或 cur.random 的映射前，先显式判断它是否为空；空指针应保持为空，而不是参与映射查询。

为什么是深拷贝​

验证复制结果时，不能只比较值序列。还应确认：

  1. 每个新节点都不是对应旧节点；
  2. next 与 random 指向的新节点下标和原链表一致；
  3. 新链表的任一连接都不指向旧节点集合。

两遍映射正好保证这些条件：所有边都从新节点连向映射得到的新节点。

其他思路​

也可以把复制节点暂时穿插在旧节点之后，再拆分两条链表，从而把额外映射空间降为常数。该方法会短暂修改原链表，连接恢复步骤更容易出错；本章采用关系更直接、便于验证的映射解法。

代码实现​

C++17
#include <unordered_map>
using namespace std;

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> copies;
        for (Node* cur = head; cur != nullptr; cur = cur->next) {
            copies[cur] = new Node(cur->val);
        }
        for (Node* cur = head; cur != nullptr; cur = cur->next) {
            copies[cur]->next = cur->next == nullptr ? nullptr : copies[cur->next];
            copies[cur]->random =
                cur->random == nullptr ? nullptr : copies[cur->random];
        }
        return head == nullptr ? nullptr : copies[head];
    }
};

复杂度分析​

  • 时间复杂度：O(n)，两次遍历均为线性。
  • 空间复杂度：O(n)，映射为每个旧节点保存一个新节点对应关系。

常见误区​

  • 以节点值为映射键，遇到重复值时覆盖对应关系。
  • 只创建节点，不恢复 random 指针。
  • 把新节点的连接直接指向旧节点，得到浅拷贝。

模式迁移​

“先建立对象映射，再恢复关系”可迁移到图克隆；对象有多种引用边时，键必须是对象身份，第二阶段再逐类恢复各条边。