友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

微信

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

138. 随机链表的复制

LeetCode - 138. 随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

  • val：一个表示 Node.val 的整数。

  • random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1：

0138 01 
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

0138 02 
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

0138 03 
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

提示：

  • 0 <= n <= 1000

  • -104 <= Node.val <= 104

  • Node.random 为 null 或指向链表中的节点。

思路分析

这道题可以使用类似 133. 克隆图 的解法来求解。

0138 10
0138 11

新旧节点相连的解法非常精妙！

使用 Map 的解法也好巧妙啊：先建立旧新映射，然后建立链表链接。

  • 一刷

  • 二刷

  • 三刷

 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

/**
 * Runtime: 0 ms, faster than 100.00% of Java online submissions for Copy List with Random Pointer.
 *
 * Memory Usage: 40.6 MB, less than 5.61% of Java online submissions for Copy List with Random Pointer.
 *
 * Copy from: https://leetcode.com/problems/copy-list-with-random-pointer/discuss/43488/Java-O(n)-solution[Java O(n) solution - LeetCode Discuss]
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2020-01-07 22:21
 */
public Node copyRandomList(Node head) {
    if (Objects.isNull(head)) {
        return null;
    }
    Map<Node, Node> dadToChildMap = new HashMap<>();
    Node current = head;
    while (Objects.nonNull(current)) {
        dadToChildMap.put(current, new Node(current.val));
        current = current.next;
    }

    current = head;
    while (Objects.nonNull(current)) {
        dadToChildMap.get(current).next = dadToChildMap.get(current.next);
        dadToChildMap.get(current).random = dadToChildMap.get(current.random);
        current = current.next;
    }

    return dadToChildMap.get(head);
}
/**
 * Runtime: 0 ms, faster than 100.00% of Java online submissions for Copy List with Random Pointer.
 *
 * Memory Usage: 39.2 MB, less than 5.61% of Java online submissions for Copy List with Random Pointer.
 *
 * Copy form: https://leetcode.com/problems/copy-list-with-random-pointer/discuss/43491/A-solution-with-constant-space-complexity-O(1)-and-linear-time-complexity-O(N)[A solution with constant space complexity O(1) and linear time complexity O(N) - LeetCode Discuss]
 */
public Node copyRandomListLink(Node head) {
    if (Objects.isNull(head)) {
        return null;
    }
    // 第一步：把原始链表和结果链表混编起来。
    Node acNode = head;
    while (Objects.nonNull(acNode)) {
        Node node = new Node(acNode.val);
        node.next = acNode.next;
        acNode.next = node;
        acNode = node.next;
    }
    // 第二步：复制 random 指针
    acNode = head;
    while (Objects.nonNull(acNode)) {
        Node random = acNode.random;
        if (Objects.nonNull(random)) {
            Node next = acNode.next;
            next.random = random.next;
        }
        acNode = acNode.next.next;
    }

    // 第三步：拆分出结果链表
    // Node result = head.next;
    // Node rcNode = result;
    // acNode = head;
    // while (Objects.nonNull(rcNode)) {
    //     if (Objects.nonNull(rcNode.next)) {
    //         acNode.next = rcNode.next;
    //         rcNode.next = rcNode.next.next;
    //         acNode = acNode.next;
    //     }
    //     rcNode = rcNode.next;
    // }
    // acNode.next = null;

    Node prefixHead = new Node(0);
    Node rcNode = prefixHead;
    acNode = head;
    while (Objects.nonNull(acNode)) {
        rcNode.next = acNode.next;
        acNode.next = acNode.next.next;
        acNode = acNode.next;
        rcNode = rcNode.next;
    }

    return prefixHead.next;
}

 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

/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-09-19 15:56:51
 */
public Node copyRandomList(Node head) {
  if (head == null) {
    return null;
  }
  Map<Node, Node> nodeToRandomMap = new HashMap<>();
  Map<Node, Node> oldToNewMap = new HashMap<>();
  Node dummy = new Node(0);
  Node curr = head;
  Node tail = dummy;
  while (curr != null) {
    Node newNode = new Node(curr.val);
    oldToNewMap.put(curr, newNode);
    if (curr.random != null) {
      nodeToRandomMap.put(curr, curr.random);
    }
    tail.next = newNode;
    tail = newNode;
    curr = curr.next;
  }
  curr = head;
  while (curr != null) {
    if (curr.random != null) {
      Node newNode = oldToNewMap.get(curr);
      newNode.random = oldToNewMap.get(nodeToRandomMap.get(curr));
    }
    curr = curr.next;
  }
  return dummy.next;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-11-06 22:27:13
 */
public Node copyRandomList(Node head) {
  if (head == null) {
    return null;
  }
  Map<Node, Node> map = new HashMap<>();
  Node curr = head;
  while (curr != null) {
    map.put(curr, new Node(curr.val));
    curr = curr.next;
  }
  curr = head;
  while (curr != null) {
    Node node = map.get(curr);
    node.next = map.get(curr.next);
    node.random = map.get(curr.random);
    curr = curr.next;
  }
  return map.get(head);
}

参考资料

  1. 138. 随机链表的复制 - 不用哈希表的做法

  2. 138. 随机链表的复制 - 两种实现+图解

  3. 138. 随机链表的复制 - 清晰图解

  4. 138. 随机链表的复制 - 官方题解

← Previous: 137. 只出现一次的数字 II | ↑ Up: LeetCode 解题笔记 | Next: 139. 单词拆分 →