LeetCode 第138题：复制带随机指针的链表

题目描述

给你一个长度为 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 作为传入参数。

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 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 或指向链表中的节点。

解题思路

方法一：哈希表

这道题要求我们复制一个带随机指针的链表。难点在于如何处理随机指针的指向关系。我们可以使用哈希表来建立原链表节点和新链表节点之间的映射关系。

关键点：

• 使用哈希表存储原节点到新节点的映射
• 两次遍历链表：第一次创建所有新节点，第二次设置指针关系

具体步骤：

1. 创建一个哈希表，用于存储原节点到新节点的映射
2. 第一次遍历原链表，创建所有新节点，并建立映射关系
3. 第二次遍历原链表，根据映射关系设置新节点的next和random指针
4. 返回新链表的头节点

时间复杂度：O(n)，其中n是链表的长度。需要遍历链表两次。 空间复杂度：O(n)，需要使用哈希表存储n个节点的映射关系。

方法二：原地修改

我们可以不使用额外的空间，通过修改原链表的结构来实现复制。

关键点：

• 在原链表的每个节点后插入一个新节点
• 设置新节点的random指针
• 拆分链表，得到原链表和复制链表

具体步骤：

1. 在原链表的每个节点后插入一个新节点，例如A->B->C变成A->A’->B->B’->C->C’
2. 设置新节点的random指针：如果原节点node的random指向某个节点X，则新节点node.next的random指向X.next
3. 拆分链表，得到原链表和复制链表
4. 返回复制链表的头节点

时间复杂度：O(n)，其中n是链表的长度。需要遍历链表三次。 空间复杂度：O(1)，只需要常数级别的额外空间。

图解思路

哈希表方法分析表

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

原节点	新节点	映射关系
Node(7)	Node(7)	Node(7) -> Node(7)
Node(13)	Node(13)	Node(13) -> Node(13)
Node(11)	Node(11)	Node(11) -> Node(11)
Node(10)	Node(10)	Node(10) -> Node(10)
Node(1)	Node(1)	Node(1) -> Node(1)

设置指针关系：

• 新Node(7).next = 新Node(13)，新Node(7).random = null
• 新Node(13).next = 新Node(11)，新Node(13).random = 新Node(7)
• 新Node(11).next = 新Node(10)，新Node(11).random = 新Node(1)
• 新Node(10).next = 新Node(1)，新Node(10).random = 新Node(11)
• 新Node(1).next = null，新Node(1).random = 新Node(7)

原地修改方法分析表

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

步骤1：在每个节点后插入新节点

原链表：7 -> 13 -> 11 -> 10 -> 1 插入后：7 -> 7’ -> 13 -> 13’ -> 11 -> 11’ -> 10 -> 10’ -> 1 -> 1’

步骤2：设置新节点的random指针

• 7’.random = 7.random.next = null.next = null
• 13’.random = 13.random.next = 7.next = 7’
• 11’.random = 11.random.next = 1.next = 1’
• 10’.random = 10.random.next = 11.next = 11’
• 1’.random = 1.random.next = 7.next = 7’

步骤3：拆分链表

原链表：7 -> 13 -> 11 -> 10 -> 1 复制链表：7’ -> 13’ -> 11’ -> 10’ -> 1’

代码实现

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;
        }
        
        // 创建哈希表，存储原节点到新节点的映射
        Dictionary<Node, Node> map = new Dictionary<Node, Node>();
        
        // 第一次遍历，创建所有新节点
        Node curr = head;
        while (curr != null) {
            map[curr] = new Node(curr.val);
            curr = curr.next;
        }
        
        // 第二次遍历，设置新节点的next和random指针
        curr = head;
        while (curr != null) {
            map[curr].next = curr.next != null ? map[curr.next] : null;
            map[curr].random = curr.random != null ? map[curr.random] : null;
            curr = curr.next;
        }
        
        return map[head];
    }
}

Python 实现

"""
# 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: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
        
        # 创建哈希表，存储原节点到新节点的映射
        node_map = {}
        
        # 第一次遍历，创建所有新节点
        curr = head
        while curr:
            node_map[curr] = Node(curr.val)
            curr = curr.next
        
        # 第二次遍历，设置新节点的next和random指针
        curr = head
        while curr:
            node_map[curr].next = node_map.get(curr.next)
            node_map[curr].random = node_map.get(curr.random)
            curr = curr.next
        
        return node_map[head]

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;
        }
        
        // 创建哈希表，存储原节点到新节点的映射
        unordered_map<Node*, Node*> nodeMap;
        
        // 第一次遍历，创建所有新节点
        Node* curr = head;
        while (curr) {
            nodeMap[curr] = new Node(curr->val);
            curr = curr->next;
        }
        
        // 第二次遍历，设置新节点的next和random指针
        curr = head;
        while (curr) {
            nodeMap[curr]->next = curr->next ? nodeMap[curr->next] : nullptr;
            nodeMap[curr]->random = curr->random ? nodeMap[curr->random] : nullptr;
            curr = curr->next;
        }
        
        return nodeMap[head];
    }
};

执行结果

C# 实现

• 执行用时：84 ms
• 内存消耗：40.1 MB

Python 实现

• 执行用时：36 ms
• 内存消耗：16.2 MB

C++ 实现

• 执行用时：8 ms
• 内存消耗：11.2 MB

性能对比

语言	执行用时	内存消耗	特点
C#	84 ms	40.1 MB	执行速度适中，内存消耗较高
Python	36 ms	16.2 MB	执行速度适中，内存消耗适中
C++	8 ms	11.2 MB	执行速度最快，内存消耗较低

代码亮点

1. 🎯 使用哈希表建立映射关系，思路清晰
2. 💡 两次遍历分别处理节点创建和指针设置，逻辑分明
3. 🔍 正确处理空节点和边界情况
4. 🎨 代码结构简洁，易于理解和维护

常见错误分析

1. 🚫 没有正确处理random指针为null的情况
2. 🚫 直接复制节点值而不是创建新节点，导致指针仍指向原链表
3. 🚫 在设置指针关系时没有使用映射表，导致指针指向错误
4. 🚫 原地修改方法中，拆分链表时指针操作错误，导致链表结构破坏

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
哈希表	O(n)	O(n)	实现简单，思路清晰	需要额外空间存储映射关系
原地修改	O(n)	O(1)	空间复杂度低	实现复杂，容易出错
递归 + 哈希表	O(n)	O(n)	代码简洁	递归调用可能导致栈溢出

相关题目

• LeetCode 133. 克隆图 - 中等
• LeetCode 1485. 克隆含随机指针的二叉树 - 中等
• LeetCode 2115. 从给定原材料中找到所有可以做出的菜 - 中等
• LeetCode 430. 扁平化多级双向链表 - 中等
• LeetCode 1490. 克隆 N 叉树 - 中等