C++中怎么利用LeetCode拷贝带有随机指针的链表

# C++中怎么利用LeetCode拷贝带有随机指针的链表

## 引言

在数据结构与算法的学习中，链表是最基础也是最重要的数据结构之一。而带有随机指针的链表（通常称为"Random List"或"Copy List with Random Pointer"）因其特殊的结构，成为面试和LeetCode中的经典题目。本文将深入探讨如何在C++中高效地解决这个问题。

## 问题描述

### 链表节点定义
```cpp
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = nullptr;
        random = nullptr;
    }
};

问题要求

给定一个链表的头节点head，每个节点包含： - val：节点值 - next：指向下一个节点的指针 - random：可能指向链表中任意节点或为nullptr

要求深拷贝这个链表，并返回新链表的头节点。

解决方案分析

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

算法步骤

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

C++实现

#include <unordered_map>

Node* copyRandomList(Node* head) {
    if (!head) return nullptr;
    
    std::unordered_map<Node*, Node*> nodeMap;
    Node* curr = head;
    
    // 第一次遍历：创建节点并建立映射
    while (curr) {
        nodeMap[curr] = new Node(curr->val);
        curr = curr->next;
    }
    
    // 第二次遍历：建立连接关系
    curr = head;
    while (curr) {
        nodeMap[curr]->next = nodeMap[curr->next];
        nodeMap[curr]->random = nodeMap[curr->random];
        curr = curr->next;
    }
    
    return nodeMap[head];
}

复杂度分析

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

方法二：节点交错法（O(n)时间+O(1)空间）

算法步骤

1. 第一次遍历：在每个原节点后插入拷贝节点
2. 第二次遍历：设置拷贝节点的random指针
3. 第三次遍历：分离两个链表

可视化过程

原链表：A -> B -> C
交错后：A -> A' -> B -> B' -> C -> C'

C++实现

Node* copyRandomList(Node* head) {
    if (!head) return nullptr;
    
    // 第一步：插入新节点
    Node* curr = head;
    while (curr) {
        Node* newNode = new Node(curr->val);
        newNode->next = curr->next;
        curr->next = newNode;
        curr = newNode->next;
    }
    
    // 第二步：设置random指针
    curr = head;
    while (curr) {
        if (curr->random) {
            curr->next->random = curr->random->next;
        }
        curr = curr->next->next;
    }
    
    // 第三步：分离链表
    curr = head;
    Node* newHead = head->next;
    Node* copyCurr = newHead;
    
    while (curr) {
        curr->next = curr->next->next;
        if (copyCurr->next) {
            copyCurr->next = copyCurr->next->next;
        }
        curr = curr->next;
        copyCurr = copyCurr->next;
    }
    
    return newHead;
}

复杂度分析

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

边界条件处理

需要特别注意的情况

1. 空链表输入：直接返回nullptr
2. 自循环节点：如node->random = node
3. random指向尾节点后的nullptr
4. 链表只有一个节点

测试用例示例

// 测试自循环
Node* testSelfLoop() {
    Node* node = new Node(1);
    node->random = node;
    return copyRandomList(node);
}

// 测试random为null
Node* testNullRandom() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->random = head;
    return copyRandomList(head);
}

性能对比

常见错误与陷阱

1. 浅拷贝问题：直接复制指针而非创建新节点

   // 错误示例！
   newNode->random = oldNode->random;  // 这是浅拷贝
   

2. 未处理nullptr：访问random前未检查是否为空

   // 危险代码！
   nodeMap[curr]->random = nodeMap[curr->random];  // 当random为null时会出错
   

3. 链表分离错误：在交错法中破坏原链表结构后未能正确恢复

扩展思考

为什么这个问题如此经典？

1. 综合考察了链表操作、哈希表、指针操作等多个知识点
2. 需要处理复杂的指针关系
3. 有多种解法可以对比

实际应用场景

• 对象图的深拷贝
• 数据库中的版本控制
• 内存快照功能实现

其他语言实现对比

Python实现示例（哈希表法）

def copyRandomList(self, head: 'Node') -> 'Node':
    if not head: return None
    node_map = {}
    
    # 第一次遍历创建节点
    curr = head
    while curr:
        node_map[curr] = Node(curr.val)
        curr = curr.next
    
    # 第二次遍历建立连接
    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]

总结

本文详细分析了LeetCode 138题”Copy List with Random Pointer”的两种主要解法。哈希表法直观易懂，适合大多数场景；而节点交错法则以巧妙的思路实现了空间优化。理解这两种方法不仅能帮助我们解决这个问题，更能提升对链表和指针操作的整体认知。

推荐练习题

1. LeetCode 138 - Copy List with Random Pointer
2. LeetCode 133 - Clone Graph（类似问题扩展到图结构）
3. LeetCode 148 - Sort List（综合链表操作）

掌握这类问题的解法，将大大提升你在面试中对复杂指针问题的处理能力。 “`