leetcode如何实现复制带随机指针的链表

# LeetCode如何实现复制带随机指针的链表

## 问题描述

LeetCode第138题"复制带随机指针的链表"(Copy List with Random Pointer)要求我们深度复制一个特殊的链表结构。这种链表的每个节点除了包含标准的`val`和`next`指针外，还包含一个可能指向链表中任意节点或为`null`的`random`指针。

```python
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random

问题分析

普通链表的复制非常简单，只需遍历原链表逐个创建新节点即可。但带随机指针的链表存在以下难点：

1. 随机指针的指向关系：新链表中节点的random指针必须正确指向新链表中的对应节点，而非原链表节点
2. 可能存在的循环引用：random指针可能形成环，需要避免无限循环
3. 时间复杂度与空间复杂度：如何在合理复杂度内完成复制

解决方案

方法一：哈希表映射法（O(N)时间，O(N)空间）

算法步骤

1. 第一次遍历：创建所有新节点，并用哈希表建立原节点到新节点的映射
2. 第二次遍历：通过哈希表完善新节点的next和random指针关系

def copyRandomList(head: 'Node') -> 'Node':
    if not head:
        return None
    
    # 建立原节点到新节点的映射
    mapping = {}
    curr = head
    while curr:
        mapping[curr] = Node(curr.val)
        curr = curr.next
    
    # 设置新节点的next和random指针
    curr = head
    while curr:
        if curr.next:
            mapping[curr].next = mapping[curr.next]
        if curr.random:
            mapping[curr].random = mapping[curr.random]
        curr = curr.next
    
    return mapping[head]

复杂度分析

• 时间复杂度：O(N)，两次线性遍历
• 空间复杂度：O(N)，哈希表存储所有节点映射

方法二：节点穿插法（O(N)时间，O(1)空间）

算法步骤

1. 第一次遍历：在每个原节点后插入对应的新节点

   
   原链表：A -> B -> C
   穿插后：A -> A' -> B -> B' -> C -> C'
   

2. 第二次遍历：设置新节点的random指针
3. 第三次遍历：分离新旧链表

def copyRandomList(head: 'Node') -> 'Node':
    if not head:
        return None
    
    # 1. 在每个原节点后插入新节点
    curr = head
    while curr:
        new_node = Node(curr.val)
        new_node.next = curr.next
        curr.next = new_node
        curr = new_node.next
    
    # 2. 设置新节点的random指针
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random.next
        curr = curr.next.next
    
    # 3. 分离两个链表
    curr = head
    new_head = head.next
    while curr:
        temp = curr.next
        curr.next = temp.next
        if temp.next:
            temp.next = temp.next.next
        curr = curr.next
    
    return new_head

复杂度分析

• 时间复杂度：O(N)，三次线性遍历
• 空间复杂度：O(1)，仅使用常数额外空间（不考虑输出占用的空间）

边界情况处理

在实际编码中需要考虑以下边界情况：

1. 空链表输入：直接返回None
2. 单个节点：确保random指针正确处理
3. random指向自身：如A.random = A
4. 多个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]]

方法比较

常见面试问题

1. 如何处理循环引用的random指针？

   • 两种方法都能正确处理，因为哈希表记录了已创建的节点，穿插法通过原节点直接找到对应新节点

2. 为什么穿插法不需要额外空间？

   • 它利用了原链表的next指针临时存储新节点，实际上空间开销存在于新链表本身

3. 如果链表很大，哪种方法更优？

   • 在空间受限环境下，穿插法更优；否则哈希表法代码更简洁

扩展思考

1. 图的深拷贝：这道题本质上是图的深拷贝问题，每个节点是图顶点，next和random指针是边
2. 多线程环境：如果链表可能被并发修改，需要加锁或使用不可变结构
3. 持久化数据结构：如何设计数据结构使得拷贝操作更高效

总结

复制带随机指针的链表是考察对链表结构和哈希表应用的经典题目。两种主要解法各有优劣：

• 面试推荐：通常优先解释哈希表法，然后根据面试官要求优化空间复杂度
• 工程实践：哈希表法更安全可靠，不修改原链表结构
• 算法竞赛：可能更倾向空间优化的穿插法

掌握这道题有助于理解更复杂的链表操作和对象引用关系，是数据结构学习中的重要里程碑。 “`

这篇文章共计约1700字，涵盖了问题描述、解决方案、复杂度分析、边界情况、测试用例、方法比较和扩展思考等内容，采用Markdown格式编写，可直接用于技术博客或面试准备。