复制带随机指针的链表：三步法原地深拷贝详解

可以看到，复制节点的 random 指针暂时和原节点指向相同，后续需要修正。

核心代码片段

// 步骤 1：在每个原节点后插入复制节点
Node* p = head;
while (p != NULL) {
    Node* copy = new Node(p->val); // 复制原节点的值
    copy->random = p->random;      // 暂时让复制节点的 random 与原节点一致
    copy->next = p->next;          // 复制节点的 next 指向原节点的下一个节点
    p->next = copy;                // 原节点的 next 指向复制节点
    p = copy->next;                // p 跳转到下一个原节点，继续遍历
}

第二步：修正复制节点的 random 指针

核心操作：遍历插入后的链表，仅处理复制节点的 random 指针：若原节点的 random 指向节点 A，那么复制节点的 random 应指向 A 的复制节点 A'，而 A'正是 A 的下一个节点，因此只需将复制节点的 random 指向 原 random 指向的节点的 next 即可。

注意点：需要判断原节点的 random 是否为 NULL，若为 NULL，复制节点的 random 也保持 NULL，无需处理。

图形演示

待修正的链表（复制节点 random 未修正）：

1 → 1' → 2 → 2' → 3 → 3' → NULL
|   |   |   |   |   |
v   v   v   v   v   v
3   3   1   1   NULL NULL

修正后（复制节点 random 指向对应复制节点）：

1 → 1' → 2 → 2' → 3 → 3' → NULL
|   |   |   |   |   |
v   v   v   v   v   v
3   3'  1   1'  NULL NULL

此时，所有复制节点的 next 和 random 指针均已指向正确位置，仅剩最后一步拆分。

核心代码片段

// 步骤 2：修正复制节点的 random 指针
p = head->next; // p 指向第一个复制节点
while (p != NULL) {
    if (p->random != NULL) { // 若原 random 不为空，才需要修正
        p->random = p->random->next;
    }
    // p 跳转到下一个复制节点（隔一个节点）
    p = (p->next != NULL) ? p->next->next : NULL;
}

第三步：拆分原链表与复制链表

核心操作：遍历成对的链表，将 原节点→复制节点→原节点→复制节点 的结构拆分为原链表（原节点依次连接）和复制链表（复制节点依次连接），恢复原链表的同时，得到独立的复制链表。

操作技巧：设置两个指针分别指向原节点和复制节点，依次遍历并调整 next 指针，最终复制链表的头节点为原链表头节点的下一个节点（head->next）。

图形演示

待拆分的链表（已修正 random）：

1 → 1' → 2 → 2' → 3 → 3' → NULL
|   |   |   |   |   |
v   v   v   v   v   v
3   3'  1   1'  NULL NULL

拆分后：

• 原链表：1 → 2 → 3 → NULL（恢复原状）
• 复制链表：1' → 2' → 3' → NULL（最终结果）

核心代码片段

// 步骤 3：拆分原链表和复制链表
Node* newHead = head->next; // 复制链表的头节点
Node* p1 = head;            // p1 指向原节点
Node* p2 = newHead;         // p2 指向复制节点
while (p1 != NULL) {
    p1->next = p2->next;    // 原节点的 next 指向下一个原节点
    p1 = p1->next;          // p1 后移
    if (p1 != NULL) {       // 若原节点未到末尾，复制节点继续后移
        p2->next = p1->next;
        p2 = p2->next;
    }
}
return newHead;             // 返回复制链表的头节点

完整 C++ 代码实现

结合上述三步法，补充空链表判断等边界条件处理，给出完整的 C++ 代码实现，代码逻辑清晰，注释详尽，可直接在力扣提交通过：

#include <iostream>
using namespace std;

// 定义带随机指针的链表节点
struct Node {
    int val;
    Node* next;
    Node* random;
    Node(int x) : val(x), next(NULL), random(NULL) {}
};

class Solution {
public:
    Node* copyRandomList(Node* head) {
        // 边界条件：空链表直接返回 NULL
        if (head == NULL) {
            return NULL;
        }

        // 步骤 1：在每个原节点后插入复制节点
        Node* p = head;
        while (p != NULL) {
            Node* copy = new Node(p->val);
            copy->random = p->random;
            copy->next = p->next;
            p->next = copy;
            p = copy->next;
        }

        // 步骤 2：修正复制节点的 random 指针
        p = head->next;
        while (p != NULL) {
            if (p->random != NULL) {
                p->random = p->random->next;
            }
            p = (p->next != NULL) ? p->next->next : NULL;
        }

        // 步骤 3：拆分原链表和复制链表
        Node* newHead = head->next;
        Node* p1 = head;
        Node* p2 = newHead;
        while (p1 != NULL) {
            p1->next = p2->next;
            p1 = p1->next;
            if (p1 != NULL) {
                p2->next = p1->next;
                p2 = p2->next;
            }
        }
        return newHead;
    }
};

// 测试代码（可选）
void printList(Node* head) {
    Node* p = head;
    while (p != NULL) {
        cout << "节点值：" << p->val;
        if (p->random != NULL) {
            cout << ",random 指向：" << p->random->val << endl;
        } else {
            cout << ",random 指向：NULL" << endl;
        }
        p = p->next;
    }
}

int main() {
    // 构建测试链表
    Node* n1 = new Node(1);
    Node* n2 = new Node(2);
    Node* n3 = new Node(3);
    n1->next = n2;
    n2->next = n3;
    n1->random = n3;
    n2->random = n1;
    n3->random = NULL;

    Solution s;
    Node* copyHead = s.copyRandomList(n1);
    cout << "复制链表的节点信息：" << endl;
    printList(copyHead);
    return 0;
}

算法性能分析

时间复杂度

算法全程对链表进行三次遍历：插入复制节点一次、修正 random 指针一次、拆分链表一次。每次遍历的时间复杂度为 O(n)，总时间复杂度为 O(n)（时间复杂度不考虑常数项，3n 最终简化为 n）。

空间复杂度

算法仅使用了常数个指针变量（p、p1、p2、newHead 等），未使用额外的数组、哈希表等数据结构，所有操作均在原链表上完成，因此空间复杂度为 O(1)。

对比哈希表法

除了本次的三步法，解决该问题还有哈希表映射法：先复制所有节点，用哈希表存储 原节点→复制节点 的映射，再遍历处理 next 和 random 指针。该方法的时间复杂度也是 O(n)，但空间复杂度为 O(n)（需要存储 n 个节点的映射），相比之下，三步法是更优的原地解法。

解题总结与拓展

解题核心要点

1. 原地插入复制节点是关键：让复制节点与原节点紧邻，将'随机的指向关系'转化为'固定的紧邻关系'，无需额外存储映射；
2. 分步骤处理更清晰：将复杂的复制问题拆分为'插入→修正→拆分'三个简单步骤，逐个突破，降低思维难度；
3. 边界条件不可忽视：必须判断原链表是否为空，同时处理 random 指针为 NULL 的情况，避免空指针异常。

算法拓展

本题的三步法是链表原地操作的经典应用，这类思路还可迁移到其他链表问题中，例如：

1. 链表的原地反转（多指针法）；
2. 寻找链表的中间节点（快慢指针法）；
3. 合并两个有序链表（原地合并）。

掌握链表的指针操作技巧，理解'分步骤处理'和'原地操作'的思想，能让我们更轻松地应对各类链表算法题。LeetCode 138 题作为基础经典题，是锻炼链表思维的绝佳素材，吃透这道题，后续的复杂链表问题也能迎刃而解！