跳转至

138. 随机链表的复制

LeetCode 1381 · 中等 · 链表

题

链表节点除了 next 还有一个 random 指针，可以指向链表里任意节点或空。做一份深拷贝：新链表全是新节点，新节点的 next、random 都只指向新节点，结构和原链表一模一样。

例：[[7,null],[13,0],[11,4],[10,2],[1,0]]（每项是 [值, random 指向的下标]）→ 复制出同样结构的一份。

一句话

难点是 random 可能指向还没建出来的节点——先把所有副本建好，再按「原节点 → 副本」的映射连线。

关键技巧

深拷贝 = 建映射 + 按映射连线。 原节点 x.random = y，副本就该是 copy(x).random = copy(y)。只要能 \(O(1)\) 查到 copy(·)，两遍扫描就够：第一遍建所有副本，第二遍连 next 和 random。哈希表是最直接的映射。

把映射藏进链表结构里。 把每个副本插在原节点身后：A→A'→B→B'→…。这样 copy(x) 就是 x.next，于是 x.next.random = x.random.next——映射不占额外空间。最后把交织的链拆成两条，原链表恢复原样。

三遍各干一件事：

  1. 交织：每个 x 后面插入 x'；
  2. 连 random：x'.random = x.random.next（x.random 为空则为空）；
  3. 拆分：x.next = x'.next，x'.next = x'.next.next。

第 2、3 步不能合并。 拆分会破坏 x.next == x' 的对应关系，而后面节点的 random 可能指向前面已经拆开的节点。

解

class Solution:
    def copyRandomList(self, head: Optional[Node]) -> Optional[Node]:
        copy = {None: None}  # 原节点 -> 副本，None 映射到 None 省掉判空
        cur = head
        while cur:
            copy[cur] = Node(cur.val)
            cur = cur.next
        cur = head
        while cur:
            copy[cur].next = copy[cur.next]
            copy[cur].random = copy[cur.random]
            cur = cur.next
        return copy[head]

时间 \(O(n)\)，空间 \(O(n)\)。

class Solution:
    def copyRandomList(self, head: Optional[Node]) -> Optional[Node]:
        if not head:
            return None
        cur = head
        while cur:  # A->B  =>  A->A'->B
            cur.next = Node(cur.val, cur.next)
            cur = cur.next.next
        cur = head
        while cur:  # copy(x) 就是 x.next
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next
        new_head, cur = head.next, head
        while cur:  # 拆开，原链表复原
            dup = cur.next
            cur.next = dup.next
            dup.next = dup.next.next if dup.next else None
            cur = cur.next
        return new_head

时间 \(O(n)\)，空间 \(O(1)\)（不计输出）。

延伸

  • 图的深拷贝同理：133. 克隆图2 用哈希表记「原节点 → 副本」，DFS/BFS 时遇到见过的直接取副本，防止环上无限复制。
  • 哈希版里 {None: None} 这个小技巧，把 next、random 为空的判断全省掉了。
  • 坑：交织法的第 3 步必须把原链表也复原；LeetCode 判题会检查原链表没被改动。
  • 其他链表基础模块：206. 反转链表、21. 合并两个有序链表。
自测 
class Node:
    def __init__(self, x: int, next: Node = None, random: Node = None):
        self.val = int(x)
        self.next = next
        self.random = random


def build(pairs):
    nodes = [Node(v) for v, _ in pairs]
    for i, (_, r) in enumerate(pairs):
        if i + 1 < len(nodes):
            nodes[i].next = nodes[i + 1]
        nodes[i].random = nodes[r] if r is not None else None
    return nodes[0] if nodes else None


def dump(head):
    nodes, cur = [], head
    while cur:
        nodes.append(cur)
        cur = cur.next
    idx = {id(n): i for i, n in enumerate(nodes)}
    return [[n.val, idx[id(n.random)] if n.random else None] for n in nodes], nodes


s = Solution()
for pairs in ([[7, None], [13, 0], [11, 4], [10, 2], [1, 0]], [[1, 1], [2, 1]], [[3, None], [3, 0], [3, None]]):
    head = build(pairs)
    before = dump(head)[1]
    got, copied = dump(s.copyRandomList(head))
    assert got == pairs
    assert not {id(n) for n in copied} & {id(n) for n in before}  # 全是新节点
    assert dump(head)[0] == pairs  # 原链表没被改坏
assert s.copyRandomList(None) is None

  1. LeetCode 138，2026-09-29 读。 ↩

  2. 133. 克隆图，2026-09-29 读。 ↩