题目描述

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

解题思路

本题的难点在于处理 random 指针。由于 random 指针可以指向链表中的任意节点，在普通遍历中，我们可能还没有创建该目标节点，导致无法直接设置 random 指针。

使用哈希表可以优雅地解决这个问题，具体分为两趟遍历：

第一趟遍历：创建所有新节点，并建立原节点到新节点的映射关系（map<原节点, 新节点>）。此时新节点的 next 和 random 指针暂时为 null。这一步确保了所有节点都已经被创建，后续可以放心地引用它们。

第二趟遍历：再次遍历原链表，通过哈希表查找：

  • 当前新节点的 next 应该指向 map.get(原节点.next)（即原节点 next 对应的新节点）
  • 当前新节点的 random 应该指向 map.get(原节点.random)（即原节点 random 对应的新节点）

由于 HashMap 中 map.get(null) 返回 null，所以当 random 指向空时也能正确处理。

这种方法直观易懂，两趟遍历即可完成深拷贝。

复杂度分析

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package code.J138;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class J138 {
    private static class Node {
        int val;
        Node next;
        Node random;
        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            Node newNode = map.get(cur);
            newNode.next = map.get(cur.next);
            newNode.random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}