• 示例工程
• 教程

导读

本文围绕《剑指 Offer（第 2 版）》第 35 题“复杂链表的复制”展开，完整讲解复杂链表（含next与random双指针）的定义、输入输出格式与边界条件，并基于 doocs/leetcode 仓库中该题的 14 个源码文件，深入剖析“哈希表”与“拼接 + 拆分”两种解法在 Python、Java、C++、Go、JavaScript、C#、Swift 等多语言下的实现细节。读完本文，你将掌握复杂链表复制这一经典面试题的两种标准解法，并能直接对照仓库源码完成多语言落地。

题目背景与复杂链表定义

本题收录于《剑指 Offer（第 2 版）》，题目编号为“面试题 35. 复杂链表的复制”，难度为中等。题目要求实现copyRandomList函数，复制一个复杂链表。所谓复杂链表，是指每个节点除了有一个next指针指向下一个节点之外，还有一个random指针，它可以指向链表中的任意节点，也可以为null。因此，复制过程不仅要重建节点的线性结构，还要精确还原random指针的指向关系，这是本题的核心难点。

题目注意点中指出：本题与主站 138 题（Copy List with Random Pointer）完全相同，主站对应目录下同样维护了多语言解法，可作为交叉参考。

输入输出格式与边界条件

题目的输入采用如下序列化格式：每个节点的值后面跟随一个整数，表示其random指针指向的节点索引（从 0 开始），null表示random指向空。

示例 1

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

该示例的链表结构如下图所示，random指针呈现出向前与向后交叉的多种形态，覆盖了指针指向前驱、后继等典型情况：


示例 2

输入：head = [[1,1],[2,1]]输出：[[1,1],[2,1]]

该示例考察两个节点互相以对方为random指向对象的情况：


示例 3

输入：head = [[3,null],[3,0],[3,null]]输出：[[3,null],[3,0],[3,null]]

该示例验证当多个节点值相同时，复制结果必须保持random索引的原始语义，而非简单按值匹配。

示例 4（空链表边界）

输入：head = []输出：[]

解释：给定的链表为空（空指针），因此返回null。这一边界在“拼接 + 拆分”解法中必须显式处理，否则解引用空指针会直接出错。

题目提示（数据范围）

• -10000 <= Node.val <= 10000
• Node.random为null或指向链表中的节点
• 节点数目不超过 1000

解法一：哈希表（HashMap）

核心思路

random可能指向任意节点，复制时该指针无法按遍历顺序立刻填好。因此先复制整条链并记下“原结点 → 新结点”的映射，再按映射补齐random。

具体分为两步：

1. 遍历链表，将每个节点都复制一份，同时将复制节点通过next指针串联起来，并把“原节点 → 复制节点”的对应关系存入哈希表；
2. 再次遍历链表，根据哈希表中存储的对应关系，将复制节点的random指针连接好。

时间复杂度为 $O(n)$，空间复杂度为 $O(n)$，其中 $n$ 为链表的长度。由于哈希表需要存储全部节点的映射关系，额外空间与链表长度成正比。

Python3

""" # Definition for a Node. class Node: def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None): self.val = int(x) self.next = next self.random = random """ class Solution: def copyRandomList(self, head: "Node") -> "Node": d = {} dummy = tail = Node(0) cur = head while cur: tail.next = Node(cur.val) tail = tail.next d[cur] = tail cur = cur.next tail = dummy.next cur = head while cur: tail.random = d.get(cur.random) tail = tail.next cur = cur.next return dummy.next

Python 实现要点：利用dummy哨兵节点简化头结点的插入逻辑；第二趟遍历中使用d.get(cur.random)，当cur.random为None时自然返回None，无需额外判空。

Java

/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */ class Solution { public Node copyRandomList(Node head) { Map<Node, Node> d = new HashMap<>(); Node dummy = new Node(0); Node tail = dummy; for (Node cur = head; cur != null; cur = cur.next) { tail.next = new Node(cur.val); tail = tail.next; d.put(cur, tail); } tail = dummy.next; for (Node cur = head; cur != null; cur = cur.next) { tail.random = d.get(cur.random); tail = tail.next; } return dummy.next; } }

C++

/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { unordered_map<Node*, Node*> d; Node* dummy = new Node(0); Node* tail = dummy; for (auto cur = head; cur; cur = cur->next) { tail->next = new Node(cur->val); tail = tail->next; d[cur] = tail; } tail = dummy->next; for (auto cur = head; cur; cur = cur->next) { tail->random = d[cur->random]; tail = tail->next; } return dummy->next; } };

C++ 实现要点：使用unordered_map<Node*, Node*>以原节点指针为键、复制节点指针为值。第二趟中d[cur->random]在cur->random为NULL时会向 map 中插入空映射并返回默认空指针，结果等价于nullptr，可正常工作。

Go

/** * Definition for a Node. * type Node struct { * Val int * Next *Node * Random *Node * } */ func copyRandomList(head *Node) *Node { d := map[*Node]*Node{} dummy := &Node{} tail := dummy for cur := head; cur != nil; cur = cur.Next { tail.Next = &Node{Val: cur.Val} tail = tail.Next d[cur] = tail } tail = dummy.Next for cur := head; cur != nil; cur = cur.Next { tail.Random = d[cur.Random] tail = tail.Next } return dummy.Next }

Go 实现要点：map[*Node]*Node{}中访问不存在的键返回零值nil，因此cur.Random为nil时d[cur.Random]直接得到nil，无需判空分支。

JavaScript

/** * // Definition for a Node. * function Node(val, next, random) { * this.val = val; * this.next = next; * this.random = random; * }; */ /** * @param {Node} head * @return {Node} */ var copyRandomList = function (head) { const d = new Map(); const dummy = new Node(0); let tail = dummy; for (let cur = head; cur; cur = cur.next) { tail.next = new Node(cur.val); tail = tail.next; d.set(cur, tail); } tail = dummy.next; for (let cur = head; cur; cur = cur.next) { tail.random = d.get(cur.random); tail = tail.next; } return dummy.next; };

C#

/* // Definition for a Node. public class Node { public int val; public Node next; public Node random; public Node(int _val) { val = _val; next = null; random = null; } } */ public class Solution { public Node CopyRandomList(Node head) { Dictionary<Node, Node> d = new Dictionary<Node, Node>(); Node dummy = new Node(0); Node tail = dummy; for (Node cur = head; cur != null; cur = cur.next) { tail.next = new Node(cur.val); tail = tail.next; d[cur] = tail; } tail = dummy.next; for (Node cur = head; cur != null; cur = cur.next) { tail.random = cur.random == null ? null : d[cur.random]; tail = tail.next; } return dummy.next; } }

C# 实现要点：Dictionary不允许键为null，因此第二趟必须显式判断cur.random == null并直接赋null，这是与 Python/Go/JS 实现的一个显著差异点。

Swift

/* public class Node: Hashable { * public var val: Int * public var next: Node? * public var random: Node? * public init(_ val: Int) { * self.val = val * self.next = nil * self.random = nil * } * public static func == (lhs: Node, rhs: Node) -> Bool { * return lhs === rhs * } * public func hash(into hasher: inout Hasher) { * hasher.combine(ObjectIdentifier(self)) * } * } */ class Solution { func copyRandomList(_ head: Node?) -> Node? { var d = [Node: Node]() let dummy = Node(0) var tail: Node? = dummy var cur = head while cur != nil { tail?.next = Node(cur!.val) tail = tail?.next d[cur!] = tail cur = cur?.next } tail = dummy.next cur = head while cur != nil { tail?.random = d[cur!.random ?? Node(0)] tail = tail?.next cur = cur?.next } return dummy.next } }

Swift 实现要点：为了让Node可以作为字典的键，节点类必须遵循Hashable协议，并以对象身份（ObjectIdentifier）作为哈希依据，同时==使用引用相等（===）判断。

解法二：拼接 + 拆分（常数空间优化）

核心思路

哈希表占用线性额外空间。把副本插在原结点后面，则副本的random就是原random的后继。最后拆成两条链，空间降为常数。

具体分为三步：

1. 遍历链表，将每个节点都复制一份，并将复制节点插入到原节点的后面（形成“原节点 → 复制节点 → 原节点的下一个节点”的交错结构）；
2. 再次遍历链表，根据原节点的random指针，将复制节点的random指针连接好——由于复制节点紧跟在原节点之后，原节点random指向的节点的后继节点，恰好就是复制节点random应指向的目标；
3. 最后再遍历链表，将交错结构拆分成原链表和复制链表两条独立链表。

时间复杂度为 $O(n)$，空间复杂度为 $O(1)$（不计算返回的新链表本身），其中 $n$ 为链表的长度。该解法通过复用原链表结构消除了哈希表的额外空间开销。

Python3

""" # Definition for a Node. class Node: def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None): self.val = int(x) self.next = next self.random = random """ class Solution: def copyRandomList(self, head: "Node") -> "Node": if head is None: return None cur = head while cur: node = Node(cur.val, cur.next) cur.next = node cur = node.next cur = head while cur: if cur.random: cur.next.random = cur.random.next cur = cur.next.next ans = head.next cur = head while cur: nxt = cur.next if nxt: cur.next = nxt.next cur = nxt return ans

Python 实现要点：第一步复制时使用Node(cur.val, cur.next)同时设置新节点的值并挂接后继；拆分时对每个原节点执行cur.next = nxt.next，并通过cur = nxt沿着“原 → 副本”顺序推进，保证遍历不被打乱。

Java

/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */ class Solution { public Node copyRandomList(Node head) { if (head == null) { return null; } for (Node cur = head; cur != null;) { Node node = new Node(cur.val, cur.next); cur.next = node; cur = node.next; } for (Node cur = head; cur != null; cur = cur.next.next) { if (cur.random != null) { cur.next.random = cur.random.next; } } Node ans = head.next; for (Node cur = head; cur != null;) { Node nxt = cur.next; if (nxt != null) { cur.next = nxt.next; } cur = nxt; } return ans; } }

C++

/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { if (!head) { return nullptr; } for (Node* cur = head; cur;) { Node* node = new Node(cur->val); node->next = cur->next; cur->next = node; cur = node->next; } for (Node* cur = head; cur; cur = cur->next->next) { if (cur->random) { cur->next->random = cur->random->next; } } Node* ans = head->next; for (Node* cur = head; cur;) { Node* nxt = cur->next; if (nxt) { cur->next = nxt->next; } cur = nxt; } return ans; } };

Go

/** * Definition for a Node. * type Node struct { * Val int * Next *Node * Random *Node * } */ func copyRandomList(head *Node) *Node { if head == nil { return nil } for cur := head; cur != nil; { node := &Node{cur.Val, cur.Next, nil} cur.Next = node cur = node.Next } for cur := head; cur != nil; cur = cur.Next.Next { if cur.Random != nil { cur.Next.Random = cur.Random.Next } } ans := head.Next for cur := head; cur != nil; { nxt := cur.Next if nxt != nil { cur.Next = nxt.Next } cur = nxt } return ans }

Go 实现要点：使用结构体字面量&Node{cur.Val, cur.Next, nil}一次性完成值、后继与random的初始化，其中第三个字段显式置nil。

JavaScript

/** * // Definition for a Node. * function Node(val, next, random) { * this.val = val; * this.next = next; * this.random = random; * }; */ /** * @param {Node} head * @return {Node} */ var copyRandomList = function (head) { if (!head) { return null; } for (let cur = head; cur;) { const node = new Node(cur.val, cur.next, null); cur.next = node; cur = node.next; } for (let cur = head; cur; cur = cur.next.next) { if (cur.random) { cur.next.random = cur.random.next; } } const ans = head.next; for (let cur = head; cur;) { const nxt = cur.next; if (nxt) { cur.next = nxt.next; } cur = nxt; } return ans; };

C#

/* // Definition for a Node. public class Node { public int val; public Node next; public Node random; public Node(int _val) { val = _val; next = null; random = null; } } */ public class Solution { public Node CopyRandomList(Node head) { if (head == null) { return null; } for (Node cur = head; cur != null; ) { Node node = new Node(cur.val, cur.next); cur.next = node; cur = node.next; } for (Node cur = head; cur != null; cur = cur.next.next) { if (cur.random != null) { cur.next.random = cur.random.next; } } Node ans = head.next; for (Node cur = head; cur != null; ) { Node nxt = cur.next; if (nxt != null) { cur.next = nxt.next; } cur = nxt; } return ans; } }

两种解法对比与选型建议

选择建议：面试中可以先给出思路更直观的哈希表解法，再主动优化为拼接 + 拆分解法，展示对空间复杂度的控制能力。两种解法都只需遍历有限次链表，时间复杂度相同，核心差异在于是否接受 $O(n)$ 的哈希表额外空间。

仓库源码佐证

doocs/leetcode 仓库在 lcof/面试题35. 复杂链表的复制 目录下为该题维护了完整的题解文档与 14 个多语言源码文件，其中Solution.*为哈希表解法，Solution2.*为拼接 + 拆分解法：

• 哈希表解法：Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.js、Solution.cs、Solution.swift
• 拼接 + 拆分解法：Solution2.py、Solution2.java、Solution2.cpp、Solution2.go、Solution2.js、Solution2.cs

同时，本题与主站 138 题（Copy List with Random Pointer）为同一问题，主站目录下还额外提供了 TypeScript 实现（Solution.ts/Solution2.ts），并配有问题插图目录，可作为跨题号对照学习的补充素材。

总结

复杂链表的复制考察的是在指针关系无法顺序推导时，如何借助辅助映射或结构变换完成深拷贝。哈希表解法以空间换实现简单，拼接 + 拆分解法以三步遍历在 $O(1)$ 空间内完成同样任务。两种思路在多语言下均有规整的模板式写法，掌握它们即可从容应对本题及其变体（如 LeetCode 138 题），并能灵活迁移到“含跨层引用结构复制”一类问题中。

• 示例工程
• 教程