138. 随机链表的复制

力扣题目链接 (opens new window)

题目描述

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

• val：一个表示 Node.val 的整数。
• random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 0 <= n <= 1000
• -10^4 <= Node.val <= 10^4
• Node.random 为 null 或指向链表中的节点。

思路

这道题和普通的链表复制不一样，难点在于 random 指针。

如果只有 next 指针，直接遍历一遍链表，逐个创建新节点就行了。但这道题每个节点还有一个 random 指针，可能指向链表中的任意节点。

关键问题是：当我们复制节点 A 的时候，它的 random 指向节点 B，但此时节点 B 的副本可能还没创建，怎么办？

这就需要建立原节点和新节点之间的映射关系。

想到映射，就应该想到哈希表了。

哈希表法

用哈希表记录每个原节点对应的新节点。

具体分两步：

第一步：遍历原链表，创建所有新节点

只复制节点的值，暂时不管 next 和 random 指针，把每个「原节点 → 新节点」的映射关系存到哈希表中。

第二步：再次遍历原链表，建立新节点之间的指针关系

此时所有新节点都已经创建好了，可以通过哈希表找到任意原节点对应的新节点。

对于原链表中的节点 cur：

• newNode->next = map[cur->next]（通过哈希表找到 cur->next 对应的新节点）
• newNode->random = map[cur->random]（通过哈希表找到 cur->random 对应的新节点）

这样就完成了深拷贝。

原地法（进阶）

还有一种不用额外空间的做法：在原链表的每个节点后面插入一个新节点，形成 原节点1 → 新节点1 → 原节点2 → 新节点2 → ... 的结构。

这样新节点就紧跟在对应的原节点后面，不需要哈希表也能找到映射关系。

但这种方法需要三次遍历，且会临时修改原链表结构，代码复杂度更高。对于面试来说，哈希表法更清晰，更不容易出错。

模拟过程

以示例 1 为例：[[7,null],[13,0],[11,4],[10,2],[1,0]]

第一次遍历：创建所有新节点并建立映射

遍历原链表，为每个原节点创建对应的新节点（暂时只复制值），并将映射关系存入哈希表。

第二次遍历：建立新节点的指针关系

再次遍历原链表，通过哈希表找到对应的新节点，设置新节点的 next 和 random 指针。

以原节点 13 为例：

• 它的 next 指向原节点 11，所以新节点 13' 的 next 应该指向新节点 11'（通过 map 查找）
• 它的 random 指向原节点 7，所以新节点 13' 的 random 应该指向新节点 7'（通过 map 查找）

最后返回新链表的头节点。

解题代码

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) return nullptr;
        
        unordered_map<Node*, Node*> map; // 原节点 -> 新节点的映射
        
        // 第一次遍历：创建所有新节点
        Node* cur = head;
        while (cur != nullptr) {
            map[cur] = new Node(cur->val); // 只复制值，指针暂不处理
            cur = cur->next;
        }
        
        // 第二次遍历：建立新节点的指针关系
        cur = head;
        while (cur != nullptr) {
            map[cur]->next = map[cur->next];     // 通过哈希表找到对应的新节点
            map[cur]->random = map[cur->random]; // random 也通过哈希表映射
            cur = cur->next;
        }
        
        return map[head]; // 返回新链表的头节点
    }
};

复杂度分析

• 时间复杂度：O(n)，两次遍历链表
• 空间复杂度：O(n)，哈希表存储 n 个节点的映射关系

其他语言

Python3

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
        
        node_map = {}  # 原节点 -> 新节点的映射
        
        # 第一次遍历：创建所有新节点
        cur = head
        while cur:
            node_map[cur] = Node(cur.val)
            cur = cur.next
        
        # 第二次遍历：建立新节点的指针关系
        cur = head
        while cur:
            if cur.next:
                node_map[cur].next = node_map[cur.next]
            if cur.random:
                node_map[cur].random = node_map[cur.random]
            cur = cur.next
        
        return node_map[head]

Java

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        
        Map<Node, Node> map = new HashMap<>();
        
        // 第一次遍历：创建所有新节点
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        
        // 第二次遍历：建立新节点的指针关系
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        
        return map.get(head);
    }
}

Go

func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }
    
    nodeMap := make(map[*Node]*Node)
    
    // 第一次遍历：创建所有新节点
    cur := head
    for cur != nil {
        nodeMap[cur] = &Node{Val: cur.Val}
        cur = cur.Next
    }
    
    // 第二次遍历：建立新节点的指针关系
    cur = head
    for cur != nil {
        nodeMap[cur].Next = nodeMap[cur.Next]
        nodeMap[cur].Random = nodeMap[cur.Random]
        cur = cur.Next
    }
    
    return nodeMap[head]
}

JS

var copyRandomList = function(head) {
    if (!head) return null;
    
    const map = new Map(); // 原节点 -> 新节点的映射
    
    // 第一次遍历：创建所有新节点
    let cur = head;
    while (cur) {
        map.set(cur, new Node(cur.val));
        cur = cur.next;
    }
    
    // 第二次遍历：建立新节点的指针关系
    cur = head;
    while (cur) {
        map.get(cur).next = map.get(cur.next) || null;
        map.get(cur).random = map.get(cur.random) || null;
        cur = cur.next;
    }
    
    return map.get(head);
};

与代码随想录联系

这道题的核心在于用哈希表建立映射关系。

我在代码随想录哈希表章节里，详细讲解过什么时候用哈希表，以及如何设计 key 和 value。

如果想进一步学习哈希表的应用，可以看一下 代码随想录哈希表章节。

本题和普通链表题目的区别在于多了 random 指针，需要建立原节点到新节点的映射。这种"建立对应关系"的场景，哈希表是最直接的选择。

<function_calls> /Users/kama/Documents/workplace/vuepress-leetcode-master-refactor/docs/hot100/0138.copy-list-with-random-pointer.md