codeforces-go 题解精讲：LeetCode 138 复制带随机指针的链表（O(1) 空间交错链表法）

本文以 leetcode/problems/138.md 题解为骨架，深入拆解 LeetCode 138「复制带随机指针的链表」的原地解法：如何不借助哈希表，仅凭交错链表的巧妙构造，在 O(1) 额外空间内完成深拷贝。读完本文，你将掌握"复制穿插 → 设置 random → 分离还原"三步法的完整推导与五种语言的落地方案，并能顺带理解与 328 奇偶链表同源的"链表分离"技巧。

题目背景与深拷贝的定义

LeetCode 138 题（Copy List with Random Pointer）给出的链表节点包含三个字段：val、next 和 random。其中 random 指针可能指向链表中的任意一个节点，也可能指向 null。

所谓深拷贝，要求返回的新链表中的每个节点都是新创建的，且这些新节点的 random 指针都指向新链表中的相应节点——也就是说，新旧两条链表在结构上完全同构，但不能共享任何节点。

用 Go 描述节点结构大致如下（对应 LeetCode 官方定义 Node{Val int; Next *Node; Random *Node}）：

type Node struct {
    Val    int
    Next   *Node
    Random *Node
}

仓库的 leetcode/testutil/predefined_type.go 中为链表测试定义的单向节点结构 ListNode（Val int; Next *ListNode）以及配套的构造、取值辅助函数（BuildListNodeFromInts、Values、Nodes 等），可以帮你理解这类链表题目在本地测试驱动中是如何被构造、遍历与断言的。

为什么不能简单遍历复制

如果链表里没有 random 指针，问题非常简单：只需在遍历链表的同时，依次复制每个节点（创建新节点并复制 val），添加到新链表的末尾即可。整个过程与"数组浅拷贝"没有本质区别。

一旦引入 random 指针，问题立刻变得复杂：在复制节点时，我们并不知道 random 指向的那个节点，在新链表中对应哪个节点。新节点尚未全部创建完毕，就无法为新节点的 random 指针确定目标。

最常见的解决思路是使用哈希表：记录原链表节点到新链表节点的映射（map），第一遍遍历创建所有新节点并建立映射，第二遍遍历时根据 cur.random 查到新链表中对应的节点。这样时间 O(n)、空间 O(n)。

但本题可以做到 O(1) 额外空间。核心洞察是：不需要哈希表，我们可以把新链表和旧链表"混在一起"。

核心思路：把新旧链表交错拼接

以链表 1 → 2 → 3 为例，依次复制每个节点（创建新节点并复制 val 和 next），把新节点直接插到原节点的后面，形成一个交错链表：

1 → 1' → 2 → 2' → 3 → 3'

这样做的好处立竿见影：原链表节点的下一个节点，就是其对应的新链表节点。也就是说，任意原节点 cur，它的拷贝就是 cur.next，无需任何映射表即可在常数时间内定位。

接下来分三步完成深拷贝：

1. 复制穿插：遍历原链表，为每个节点创建拷贝节点，插入在原节点之后；
2. 设置 random：遍历交错链表中的原链表节点，假如节点 1 的 random 指向节点 3，那么新节点 1' 的 random 就应指向 3 的下一个节点 3'（即 cur.random.next），这样就完成了对 random 指针的复制；
3. 分离还原：从交错链表中分离出 1' → 2' → 3'，即为深拷贝后的链表，这一步的做法与 328. 奇偶链表 中的"拆分成两条链表"如出一辙。

⚠️ 关键注意点：不能只"删除"原链表节点 $1,2,3$ 就完事，因为题目要求原链表的 next 不能被修改。所以分离阶段必须显式地把原节点的 next 恢复回原来的指向，同时把拷贝节点串联成新链表。若只做单向的"跳过原节点"处理，会破坏原链表，导致提交判错。

多语言代码实现

Python3（写法一：直接丢弃原节点）

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        # 复制每个节点，把新节点直接插到原节点的后面
        cur = head
        while cur:
            cur.next = Node(cur.val, cur.next)
            cur = cur.next.next

        # 遍历交错链表中的原链表节点
        cur = head
        while cur:
            if cur.random:
                # 要复制的 random 是 cur.random 的下一个节点
                cur.next.random = cur.random.next
            cur = cur.next.next

        # 删除交错链表中的原链表节点，剩下的节点即为新链表
        cur = dummy = Node(0, head)
        while cur.next:
            # 删除原链表的节点，即当前节点的下一个节点
            # 如果要恢复原链表，见另一份代码【Python3 写法二】
            cur.next = cur.next.next
            cur = cur.next

        return dummy.next

Python3（写法二：完整恢复原链表）

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        # 复制每个节点，把新节点直接插到原节点的后面
        cur = head
        while cur:
            cur.next = Node(cur.val, cur.next)
            cur = cur.next.next

        # 遍历交错链表中的原链表节点
        cur = head
        while cur:
            if cur.random:
                # 要复制的 random 是 cur.random 的下一个节点
                cur.next.random = cur.random.next
            cur = cur.next.next

        # 把交错链表分离成两个链表
        tail = dummy = Node(0, head)
        cur = head
        while cur:
            copy = cur.next  # 新节点
            tail.next = copy  # 把新节点插在 tail 的后面，构建新的链表
            cur.next = copy.next  # 恢复原节点的 next
            cur = cur.next
            tail = tail.next

        return dummy.next

写法一与写法二的前两步完全相同，差异只在分离阶段：写法二在构建新链表的同时把原节点的 next 逐一还原，保证传入的 head 在函数返回后依然是一条完整可遍历的原链表，更符合"原链表不被修改"的语义，是更严谨的工程写法。

Java

class Solution {
    public Node copyRandomList(Node head) {
        // 复制每个节点，把新节点直接插到原节点的后面
        for (Node cur = head; cur != null; cur = cur.next.next) {
            cur.next = new Node(cur.val, cur.next);
        }

        // 遍历交错链表中的原链表节点
        for (Node cur = head; cur != null; cur = cur.next.next) {
            if (cur.random != null) {
                // 要复制的 random 是 cur.random 的下一个节点
                cur.next.random = cur.random.next;
            }
        }

        // 把交错链表分离成两个链表
        Node dummy = new Node(0);
        Node tail = dummy;
        for (Node cur = head; cur != null; cur = cur.next, tail = tail.next) {
            Node copy = cur.next; // 新节点
            tail.next = copy; // 把新节点插在 tail 的后面，构建新的链表
            cur.next = copy.next; // 恢复原节点的 next
        }

        return dummy.next;
    }
}

C++

class Solution {
public:
    Node* copyRandomList(Node* head) {
        // 复制每个节点，把新节点直接插到原节点的后面
        for (Node* cur = head; cur; cur = cur->next->next) {
            cur->next = new Node(cur->val, cur->next, nullptr);
        }

        // 遍历交错链表中的原链表节点
        for (Node* cur = head; cur; cur = cur->next->next) {
            if (cur->random) {
                // 要复制的 random 是 cur->random 的下一个节点
                cur->next->random = cur->random->next;
            }
        }

        // 把交错链表分离成两个链表
        Node dummy(0);
        Node* tail = &dummy;
        for (Node* cur = head; cur; cur = cur->next, tail = tail->next) {
            Node* copy = cur->next; // 新节点
            tail->next = copy; // 把新节点插在 tail 的后面，构建新的链表
            cur->next = copy->next; // 恢复原节点的 next
        }

        return dummy.next;
    }
};

C

struct Node* copyRandomList(struct Node* head) {
    // 复制每个节点，把新节点直接插到原节点的后面
    for (struct Node* cur = head; cur; cur = cur->next->next) {
        struct Node* copy = malloc(sizeof(struct Node));
        copy->val = cur->val;
        copy->next = cur->next;
        copy->random = NULL;
        cur->next = copy;
    }

    // 遍历交错链表中的原链表节点
    for (struct Node* cur = head; cur; cur = cur->next->next) {
        if (cur->random) {
            // 要复制的 random 是 cur->random 的下一个节点
            cur->next->random = cur->random->next;
        }
    }

    // 把交错链表分离成两个链表
    struct Node dummy;
    struct Node* tail = &dummy;
    for (struct Node* cur = head; cur; cur = cur->next, tail = tail->next) {
        struct Node* copy = cur->next; // 新节点
        tail->next = copy; // 把新节点插在 tail 的后面，构建新的链表
        cur->next = copy->next; // 恢复原节点的 next
    }

    return dummy.next;
}

C 语言版本需要手动 malloc 新节点，并且创建拷贝节点时先把 random 显式置空（后续第二阶段再填充），体现了该题在无 GC 语言下的内存管理差异。

Go

func copyRandomList(head *Node) *Node {
    // 复制每个节点，把新节点直接插到原节点的后面
    for cur := head; cur != nil; cur = cur.Next.Next {
        cur.Next = &Node{Val: cur.Val, Next: cur.Next}
    }

    // 遍历交错链表中的原链表节点
    for cur := head; cur != nil; cur = cur.Next.Next {
        if cur.Random != nil {
            // 要复制的 random 是 cur.Random 的下一个节点
            cur.Next.Random = cur.Random.Next
        }
    }

    // 把交错链表分离成两个链表
    dummy := Node{}
    tail := &dummy
    for cur := head; cur != nil; cur, tail = cur.Next, tail.Next {
        clone := cur.Next     // 新节点
        tail.Next = clone     // 把新节点插在 tail 的后面，构建新的链表
        cur.Next = clone.Next // 恢复原节点的 next
    }

    return dummy.Next
}

Go 版本与仓库 leetcode/testutil/predefined_type.go 中 ListNode 的构造方式保持一致（用 &ListNode{Val: v} 创建新节点后接到 cur.Next），这类"哑节点 + 尾指针串联"的链表构建范式在仓库的测试工具里反复出现，可直接对照参考。

JavaScript

var copyRandomList = function(head) {
    // 复制每个节点，把新节点直接插到原节点的后面
    for (let cur = head; cur; cur = cur.next.next) {
        cur.next = new _Node(cur.val, cur.next, null);
    }

    // 遍历交错链表中的原链表节点
    for (let cur = head; cur; cur = cur.next.next) {
        if (cur.random) {
            // 要复制的 random 是 cur.random 的下一个节点
            cur.next.random = cur.random.next;
        }
    }

    // 把交错链表分离成两个链表
    const dummy = new _Node();
    let tail = dummy;
    for (let cur = head; cur; cur = cur.next, tail = tail.next) {
        const copy = cur.next; // 新节点
        tail.next = copy; // 把新节点插在 tail 的后面，构建新的链表
        cur.next = copy.next; // 恢复原节点的 next
    }

    return dummy.next;
};

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。三个阶段各遍历一次链表，每阶段内部都是常数时间操作，总遍历次数为 3n，渐进复杂度为 O(n)。
• 空间复杂度：O(1)。返回值不计入空间开销，全程只使用了若干指针变量（cur、dummy、tail、copy 等），没有额外分配与 n 相关的存储，因此原地完成了深拷贝。

与哈希表解法（O(n) 空间）相比，本解法的优势在于空间常数级；代价是代码中需要多维护一层"穿插"与"还原"的逻辑，对边界情况（空链表、random 为 null、random 指向自身）要求更细致的处理。

易错点与边界情况小结

1. 空链表：head == nil 时，三个循环体都不会进入，直接返回 dummy.Next（即 nil），正确。
2. random 为 null：第二阶段中必须用 if cur.random != nil 做判空，避免对空指针取 .Next 产生解引用错误。
3. random 指向自身：此时 cur.random.next 恰好就是新节点本身，公式 cur.next.random = cur.random.next 依然成立，无需特判。
4. 原链表不可变：分离阶段务必恢复原节点的 next，推荐直接采用"写法二"的完整还原版本。

延伸：与哈希表解法的对比及同类题

如果把题目要求放宽（例如允许修改原链表），也可以只用第一阶段的"穿插"配合后续删除完成；但在 LeetCode 的判定下必须保持原链表结构，因此分离阶段是必不可少的收尾动作。哈希表解法依然是"先映射、后回填"的通用模板，适合先想清楚正确性再优化空间的场景；而交错链表法把"原节点与拷贝节点的对应关系"编码进了链表结构本身，是链表题中"以结构换空间"的代表性技巧。

正如题解中所提示的，分离交错链表的操作与 328 奇偶链表（Odd Even Linked List）中"把一条链表拆成奇数位与偶数位两条链表"的模式高度同源——都是通过指针重连在两条逻辑链之间切换，理解其中任意一道，另一道的分离阶段即可触类旁通。

仓库中的上下文

本文对应的完整题解文档位于 leetcode/problems/138.md，与仓库 leetcode/problems 目录下的其他题解（115、128、135、139 等）并列存放，构成该项目的 LeetCode 题解集。若要在本地验证链表操作的正确性，可参考 leetcode/testutil/predefined_type.go 中 ListNode 的 buildListNode（从形如 [1,2,3] 的字符串构造链表）、Values（导出节点值序列）、BuildListNodeFromInts 等辅助函数，它们为链表类题目的样例构造与结果断言提供了开箱即用的工具。