LeetCode 热题 100 138. 随机链表的复制

LeetCode 热题 100 | 138. 随机链表的复制

大家好，今天我们来解决一道经典的链表问题——随机链表的复制。这道题在 LeetCode 上被标记为中等难度，要求深拷贝一个带有随机指针的链表。

问题描述

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random，该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。

示例 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. 三步法：

   • 第一步：在每个原节点后面插入一个新节点，新节点的值与原节点相同。
   • 第二步：设置新节点的 random 指针，利用原节点的 random 指针来设置新节点的 random 指针。
   • 第三步：将原链表和新链表分离，恢复原链表，提取新链表。

2. 哈希表法：

   • 使用一个哈希表存储原节点和新节点的映射关系。
   • 遍历原链表，创建新节点并设置 next 和 random 指针。

方法一：三步法

步骤 1：复制每个节点并插入到原节点后面

current = head
while current:
    new_node = Node(current.val)
    new_node.next = current.next
    current.next = new_node
    current = new_node.next

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

current = head
while current:
    if current.random:
        current.next.random = current.random.next
    current = current.next.next

步骤 3：分离原链表和新链表

current = head
new_head = head.next if head else None
while current:
    new_node = current.next
    current.next = new_node.next
    if new_node.next:
        new_node.next = new_node.next.next
    current = current.next

完整代码实现

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None
        
        # 第一步：复制每个节点并插入到原节点后面
        current = head
        while current:
            new_node = Node(current.val)
            new_node.next = current.next
            current.next = new_node
            current = new_node.next
        
        # 第二步：设置新节点的 random 指针
        current = head
        while current:
            if current.random:
                current.next.random = current.random.next
            current = current.next.next
        
        # 第三步：分离原链表和新链表
        current = head
        new_head = head.next
        while current:
            new_node = current.next
            current.next = new_node.next
            if new_node.next:
                new_node.next = new_node.next.next
            current = current.next
        
        return new_head

方法二：哈希表法

步骤 1：创建哈希表存储原节点和新节点的映射关系

node_map = {}
current = head
while current:
    node_map[current] = Node(current.val)
    current = current.next

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

current = head
while current:
    if current.next:
        node_map[current].next = node_map[current.next]
    if current.random:
        node_map[current].random = node_map[current.random]
    current = current.next

完整代码实现

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None
        
        # 创建哈希表存储原节点和新节点的映射关系
        node_map = {}
        current = head
        while current:
            node_map[current] = Node(current.val)
            current = current.next
        
        # 设置新节点的 next 和 random 指针
        current = head
        while current:
            if current.next:
                node_map[current].next = node_map[current.next]
            if current.random:
                node_map[current].random = node_map[current.random]
            current = current.next
        
        return node_map[head]

复杂度分析

• 三步法：

  • 时间复杂度：O(n)，其中 n 是链表的长度。每个节点被处理三次。
  • 空间复杂度：O(1)，只使用了常数级别的额外空间。

• 哈希表法：

  • 时间复杂度：O(n)，其中 n 是链表的长度。每个节点被处理两次。
  • 空间复杂度：O(n)，使用了哈希表存储原节点和新节点的映射关系。

示例运行

示例 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]]

总结

通过三步法或哈希表法，我们可以高效地完成带有随机指针的链表的深拷贝。三步法利用链表的结构特点，避免了额外的空间开销，而哈希表法则更直观，但需要额外的空间。希望这篇题解对大家有所帮助，如果有任何问题，欢迎在评论区留言讨论！

关注我，获取更多算法题解和编程技巧！