随机链表的复制

GitHub跳转原题关系图返回列表

哈希表映射旧节点到新节点，第二遍补 next/random 引用。

OJ: leetcodecn

题目 ID: copy-list-with-random-pointer

难度:普及+/提高

标签:链表哈希表cpppython

日期: 2026-07-28 22:05

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

复制带随机指针的链表，返回深拷贝。random 指针可指向任意节点或 null。

思路

哈希表第一遍遍历创建所有新节点并建立映射，第二遍遍历补全 next 和 random。O(n) 时间 O(n) 空间。

进阶：节点交错插入法（旧->新->旧->新…）可做到 O(1) 额外空间。

代码

cpp
/**
 * Author by Rainboy
 */
// main.cpp：哈希表映射，两遍遍历。
#include <bits/stdc++.h>
using namespace std;

class Node {
public:
    int val;
    Node *next;
    Node *random;

    Node(int _val) : val(_val), next(nullptr), random(nullptr) {}
};

class Solution {
public:
    Node *copyRandomList(Node *head) {
        if (!head)
            return nullptr;
        unordered_map<Node *, Node *> m;
        for (auto p = head; p; p = p->next)
            m[p] = new Node(p->val);
        for (auto p = head; p; p = p->next) {
            m[p]->next = m[p->next];
            m[p]->random = m[p->random];
        }
        return m[head];
    }
};

Node *build(istream &in, int n) {
    if (!n)
        return nullptr;
    vector<Node *> nodes(n);
    for (int i = 0, v; i < n; i++) {
        in >> v;
        nodes[i] = new Node(v);
    }
    for (int i = 0; i < n - 1; i++)
        nodes[i]->next = nodes[i + 1];
    return nodes[0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    auto head = build(cin, n);
    auto copied = Solution().copyRandomList(head);
    for (auto p = copied; p; p = p->next)
        cout << p->val << ' ';
    return 0;
}
python
#!/usr/bin/env python3
class Node:
    def __init__(self, x):
        self.val = x
        self.next = None
        self.random = None


class Solution:
    def copyRandomList(self, head: Node) -> Node:
        if not head:
            return None
        m = {}
        p = head
        while p:
            m[p] = Node(p.val)
            p = p.next
        p = head
        while p:
            m[p].next = m.get(p.next)
            m[p].random = m.get(p.random)
            p = p.next
        return m[head]


def build(arr):
    if not arr:
        return None
    nodes = [Node(v) for v in arr]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    return nodes[0]


def main() -> None:
    n = int(input())
    a = list(map(int, input().split()))
    head = build(a)
    copied = Solution().copyRandomList(head)
    while copied:
        print(copied.val, end=" ")
        copied = copied.next


if __name__ == "__main__":
    main()

复杂度

  • 时间复杂度：O(n)。
  • 空间复杂度：O(n)。

总结

拷贝指针问题中哈希表是最直观的解法。交错插入法优化了空间，但增加了实现复杂度。