如何复制带随机指针的链表？

Question

如何在不使用额外空间的情况下复制一个带有随机指针的链表？已知每个节点除了指向下一个节点的指针外，还有一个随机指针可能指向链表中的任意节点或为空。常规哈希表方法需要 O(n) 额外空间来映射原节点与新节点，面试中常被要求优化至空间复杂度 O(1)。此时需考虑在原链表中逐个插入复制节点，将新节点链接在原节点之后，再根据原节点的随机指针关系设置复制节点的随机指针，最后拆分新旧链表。该方法虽时间复杂度为 O(n)，但实现细节易出错，如指针处理不当会导致循环或丢失节点，如何正确实现三步法的逻辑衔接是关键难点。

Answer 1

如何在不使用额外空间的情况下复制一个带有随机指针的链表

在处理复杂数据结构问题时，复制一个带有随机指针（random pointer）的链表是一个经典难题。该问题不仅考验对指针操作的理解，还要求开发者具备良好的空间优化意识。本文将从基础概念出发，深入剖析三步法的核心逻辑，并通过代码示例与流程图辅助理解。

1. 问题定义与挑战分析

• 每个节点包含两个指针：next 和 random。
• random 指针可能指向链表中任意节点或为 null。
• 目标是深拷贝整个链表，包括所有节点及其指针关系。
• 常规方法使用哈希表映射原节点与新节点，空间复杂度 O(n)。
• 面试中常要求优化至 O(1) 额外空间 —— 即不能使用哈希表。
• 难点在于：如何在无映射关系的情况下正确设置新节点的 random 指针？
• 关键洞察：可以利用原链表的空间，在每个原节点后插入其副本。
• 这样，原节点的 random 指向的节点，其后继就是对应副本节点。
• 此技巧避免了显式存储映射关系。
• 最终通过三次遍历完成复制、连接 random、拆分链表。

2. 三步法详解

1. 第一步：复制节点并插入原链表 遍历原链表，为每个节点创建副本，并将其插入到原节点之后。例如：
   原链表：A → B → C 变为：A → A' → B → B' → C → C'
2. 第二步：设置复制节点的 random 指针 再次遍历链表，若原节点 cur 的 random 不为空，则： cur->next->random = cur->random->next; 因为 cur->next 是副本节点，cur->random->next 是原 random 节点的副本。
3. 第三步：拆分新旧链表 将交织的链表分离成两条独立链表：原始链和复制链。 使用双指针分别提取奇数位（原链）和偶数位（新链）节点。

3. 算法实现（C++ 示例）

struct Node {
    int val;
    Node *next;
    Node *random;
    Node(int _val) : val(_val), next(nullptr), random(nullptr) {}
};

Node* copyRandomList(Node* head) {
    if (!head) return nullptr;

    // Step 1: Clone nodes and insert after originals
    for (Node* cur = head; cur; cur = cur->next->next) {
        Node* clone = new Node(cur->val);
        clone->next = cur->next;
        cur->next = clone;
    }

    // Step 2: Assign random pointers for clones
    for (Node* cur = head; cur; cur = cur->next->next) {
        if (cur->random)
            cur->next->random = cur->random->next;
    }

    // Step 3: Split the combined list
    Node* newHead = head->next;
    for (Node* cur = head; cur; cur = cur->next) {
        Node* clone = cur->next;
        cur->next = cur->next->next;
        clone->next = clone->next ? clone->next->next : nullptr;
    }

    return newHead;
}

4. 流程图展示三步过程

graph TD A[原始链表] --> B[插入复制节点] B --> C[设置random指针] C --> D[拆分链表] subgraph Step1 B1(A) --> B2(A') B2 --> B3(B) B3 --> B4(B') end subgraph Step2 C1(A.random=B) --> C2(A'.random=B') end subgraph Step3 D1[分离A->B->...] D2[和A'->B'->...] end

5. 边界条件与易错点分析

边界情况	处理方式
空链表	直接返回 nullptr
random 指向 null	跳过赋值或设为 null
最后一个节点的 next->next 不存在	拆分时需判空
链表长度为奇数	不影响，因复制节点总数等于原节点数
循环链表	题目通常假设无环，但可扩展讨论
内存泄漏风险	C++ 中注意 new 后是否需 delete
指针覆盖顺序错误	如先改 cur->next 会导致后续节点丢失
random 指针跨链错误	确保只修改新链的 random，不影响原结构
拆分逻辑混乱	建议用独立变量追踪新旧链头尾
多线程环境安全	非本题范畴，但实际系统设计需考虑