LeetCode: 138. Copy List with Random Pointer

友情支持

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

支付宝

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

wx jikerizhi

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

138. Copy List with Random Pointer

LeetCode - Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:

Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.

Constraints:

-10000 ⇐ Node.val ⇐ 10000
Node.random is null or pointing to a node in the linked list.
Number of Nodes will not exceed 1000.

思路分析

这道题可以使用类似 133. Clone Graph 的解法来求解。

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

使用 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;
}

LeetCode: 138. Copy List with Random Pointer

友情支持

138. Copy List with Random Pointer

思路分析

参考资料