从影分身到链表复制：探索带随机指针的链表复制术

现实中的复制难题

想象你在一个派对上负责给每位宾客发派对礼物。每位宾客除了认识自己前后的人（就像链表的next指针），还认识派对上的某个"神秘朋友"（就像random指针）。现在你需要在隔壁房间布置一个一模一样的派对，让每个人都有一个"分身"，并确保这些分身之间的所有社交关系都和原派对一样。这就是我们今天要解决的随机链表复制问题的真实写照。

问题定义与难点分析

LeetCode 第138题"复制带随机指针的链表"要求我们对一个特殊的链表进行深拷贝。这个链表的每个节点除了包含指向下一个节点的next指针，还包含一个random指针，可以指向链表中的任意节点或null。

// 节点定义
class Node {
    int val;
    Node next;
    Node random;
}

为什么这题不简单？

让我们先深入理解问题的难点：

1. 循环依赖问题：就像派对上的人际关系一样，如果A的神秘朋友是B，B的神秘朋友是C，C的神秘朋友是A，这种循环依赖关系让我们无法简单地"一次性"完成复制。

2. 节点映射难题：当我们复制节点A'时，如果它的random指针指向节点B，而B还没有被复制，我们就陷入了"先有鸡还是先有蛋"的困境。

3. 空间效率考虑：如何在不使用额外空间的情况下，记住原节点和复制节点之间的对应关系？

解决思路的演进

让我们像解开一团缠绕的毛线一样，一步步理清解决方案：

方案一：哈希表映射法

就像在派对上给每个人发一个编号，然后在隔壁房间按编号复制人际关系。

具体步骤：

1. 第一遍遍历：创建所有节点的复制，并用哈希表记录原节点到新节点的映射关系
2. 第二遍遍历：根据哈希表中的映射关系，设置所有新节点的next和random指针

这种方法简单直观，但需要额外的存储空间。

方案二：节点交织法

这是一个巧妙的思路，就像让每个人的分身直接站在他们身后，这样就能轻松找到对应关系。

具体步骤：

1. 第一遍遍历：在每个原节点后面创建它的复制节点
2. 第二遍遍历：设置所有复制节点的random指针
3. 第三遍遍历：分离原始链表和复制链表

这种方法不需要额外空间，但需要三次遍历。

方案三：优化的节点标记法（一种特殊情况下的思路）

如果节点值的范围允许，我们可以用一些特殊的标记方式来记录节点间的对应关系。 但这种方法依赖于具体的数值范围限制，不是通用解法。

详细代码实现

让我们先来看哈希表映射法的实现，它最容易理解：

public Node copyRandomList(Node head) {
    // 特判：空链表直接返回null
    if (head == null) {
        return null;
    }
    
    // 创建哈希表存储原节点到新节点的映射
    Map<Node, Node> nodeMap = new HashMap<>();
    
    // 第一遍遍历：创建所有新节点
    Node curr = head;
    while (curr != null) {
        nodeMap.put(curr, new Node(curr.val));
        curr = curr.next;
    }
    
    // 第二遍遍历：设置所有新节点的指针
    curr = head;
    while (curr != null) {
        Node newNode = nodeMap.get(curr);
        newNode.next = nodeMap.get(curr.next);    // 可能是null，map会返回null
        newNode.random = nodeMap.get(curr.random); // 可能是null，map会返回null
        curr = curr.next;
    }
    
    return nodeMap.get(head);
}

再来看空间优化的节点交织法：

public Node copyRandomList(Node head) {
    if (head == null) {
        return null;
    }
    
    // 第一步：在每个原节点后插入复制节点
    Node curr = head;
    while (curr != null) {
        Node copy = new Node(curr.val);
        copy.next = curr.next;
        curr.next = copy;
        curr = copy.next;
    }
    
    // 第二步：设置复制节点的random指针
    curr = head;
    while (curr != null) {
        if (curr.random != null) {
            curr.next.random = curr.random.next;
        }
        curr = curr.next.next;
    }
    
    // 第三步：分离原始链表和复制链表
    curr = head;
    Node copyHead = head.next;
    Node currCopy = copyHead;
    while (curr != null) {
        curr.next = curr.next.next;
        if (currCopy.next != null) {
            currCopy.next = currCopy.next.next;
        }
        curr = curr.next;
        currCopy = currCopy.next;
    }
    
    return copyHead;
}

复杂度分析与比较

哈希表映射法：

• 时间复杂度：O(n)，需要两次遍历
• 空间复杂度：O(n)，需要哈希表存储映射关系
• 优点：实现简单，思路清晰
• 缺点：需要额外空间

节点交织法：

• 时间复杂度：O(n)，需要三次遍历
• 空间复杂度：O(1)，不需要额外空间
• 优点：空间效率高
• 缺点：需要修改原链表结构（虽然最后会恢复）

实际应用思考

这种深拷贝问题在实际开发中非常常见：

• 对象的深拷贝
• 图结构的复制
• 系统快照的创建
• 游戏存档的复制

核心技巧总结

1. 复杂问题分解：将问题分成创建节点和建立关联两个子问题
2. 空间换时间：用哈希表简化实现
3. 就地修改：通过调整链表结构省略额外空间
4. 分步骤处理：避免处理循环依赖导致的复杂性

小结

随机链表的复制问题教会我们：

1. 如何处理带有复杂引用关系的数据结构
2. 空间和时间效率的权衡思想
3. 通过临时修改数据结构解决复杂问题
4. 如何优雅地处理循环依赖问题

这道题是链表、哈希表和深拷贝概念的完美结合，它启发我们：

• 在处理复杂数据结构时，可以考虑分步骤进行
• 临时的数据结构修改有时能带来意想不到的便利
• 空间与时间的权衡是算法设计中永恒的主题

记住：解决复杂问题如同复制一场精心安排的派对，关键在于理清依赖关系，合理安排执行顺序！

---

作者：忍者算法 公众号：忍者算法

我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～