链表的深拷贝：带随机指针的链表的深拷贝

带随机指针的链表，说实话，是面试里的一道经典题。我第一次遇到它是在一个嵌入式项目的内存管理模块里——当时需要把一个复杂的数据结构完整复制一份，每个节点除了指向下一个节点，还有一个随机指针指向任意节点。嗯，浅拷贝肯定不行，因为两个链表会共享同一块内存，改一个就全乱了。

今天我们就来聊聊，怎么实现这种链表的深拷贝。

什么是带随机指针的链表？

先看定义。每个节点有三个字段：

• val：节点存储的数据
• next：指向下一个节点
• random：指向链表中任意一个节点（也可以是 NULL）

结构体定义长这样：

struct Node {
    int val;
    struct Node *next;
    struct Node *random;
};

你想想看，如果只是简单地把每个节点复制一遍，然后让新节点的 next 指向新复制的下一个节点——那 random 指针怎么办？它指向的是原链表中的节点，而不是新链表中的节点。这就是问题的核心。

深拷贝的难点在哪？

说白了，难点就一个：如何建立原节点和新节点之间的映射关系。

举个例子：原链表的节点 A 的 random 指向节点 C。复制之后，新链表的节点 A' 的 random 应该指向 C'，而不是 C。但我们怎么知道 C' 是哪个？

三种常见解法

我个人习惯把解法分成三类，每种都有它的适用场景。

1. 哈希表法（最直观）

用一个哈希表，把原节点和新节点一一对应存起来。第一次遍历复制节点，第二次遍历修正 random 指针。

struct Node* copyRandomList(struct Node* head) {
    if (!head) return NULL;

    // 第一步：复制每个节点，存入哈希表
    struct Node* cur = head;
    struct Node* dummy = (struct Node*)malloc(sizeof(struct Node));
    struct Node* prev = dummy;
    // 这里省略哈希表实现，实际可用数组或uthash

    while (cur) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->val = cur->val;
        newNode->next = NULL;
        newNode->random = NULL;
        // 存入哈希表：map[cur] = newNode
        prev->next = newNode;
        prev = newNode;
        cur = cur->next;
    }

    // 第二步：修正 random 指针
    cur = head;
    struct Node* newCur = dummy->next;
    while (cur) {
        if (cur->random) {
            newCur->random = map[cur->random]; // 从哈希表取出对应新节点
        }
        cur = cur->next;
        newCur = newCur->next;
    }

    struct Node* result = dummy->next;
    free(dummy);
    return result;
}

2. 原地复制法（空间 O(1)）

这个方法我特别喜欢，因为它不需要额外空间。思路是：

1. 在原链表的每个节点后面插入一个复制节点
2. 利用原节点的 random 指针，修正复制节点的 random
3. 把两个链表拆开

struct Node* copyRandomList(struct Node* head) {
    if (!head) return NULL;

    // 第一步：在每个原节点后面插入复制节点
    struct Node* cur = head;
    while (cur) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->val = cur->val;
        newNode->next = cur->next;
        newNode->random = NULL;
        cur->next = newNode;
        cur = newNode->next;
    }

    // 第二步：修正复制节点的 random 指针
    cur = head;
    while (cur) {
        if (cur->random) {
            cur->next->random = cur->random->next;
        }
        cur = cur->next->next;
    }

    // 第三步：拆开两个链表
    struct Node* newHead = head->next;
    struct Node* oldCur = head;
    struct Node* newCur = newHead;
    while (oldCur) {
        oldCur->next = oldCur->next->next;
        newCur->next = newCur->next ? newCur->next->next : NULL;
        oldCur = oldCur->next;
        newCur = newCur->next;
    }

    return newHead;
}

3. 递归法（代码简洁，但栈风险）

递归法用了一个哈希表来缓存已经复制过的节点，避免重复复制。

struct Node* copyNode(struct Node* node, struct Node** cache) {
    if (!node) return NULL;
    if (cache[node]) return cache[node]; // 已经复制过，直接返回

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->val = node->val;
    cache[node] = newNode; // 先存入缓存

    newNode->next = copyNode(node->next, cache);
    newNode->random = copyNode(node->random, cache);
    return newNode;
}

三种方法对比

方法	时间复杂度	空间复杂度	适用场景
哈希表法	O(n)	O(n)	通用，容易理解
原地复制法	O(n)	O(1)	内存受限的嵌入式环境
递归法	O(n)	O(n) + 栈空间	链表较短时

核心流程图

下面这张图展示了原地复制法的完整流程，我建议你仔细看看第二步——那是整个算法的精髓。

避坑指南

我曾经在项目里用原地复制法时踩过一个坑：拆链表的时候，如果原链表后面还有其他数据，一定要先把原链表的 next 恢复好。否则后续遍历原链表就会出问题。

另外，内存泄漏也是个常见问题。复制过程中如果 malloc 失败，记得把已经分配的内存释放掉。我一般会写一个辅助函数来统一处理。

嗯，今天就聊到这。代码写完了记得跑几个测试用例，特别是 random 指向自身或者形成环的情况——这些边界条件最容易出问题。