[LeetCode] 138. Copy List with Random Pointer

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

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random –> Y, then for the corresponding two nodes x and y in the copied list, x.random –> y.

Return the head of the copied linked 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) that the random pointer points to, or null if it does not point to any node.
Your code will only be given the head of the original linked list.

Example 1:
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:
Example 2
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

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

Constraints:
0 <= n <= 1000
-104 <= Node.val <= 104
Node.random is null or is pointing to some node in the linked list.

复制带随机指针的链表。

给你一个长度为 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 作为传入参数。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/copy-list-with-random-pointer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

什么叫做深度复制

明确一下什么叫做深度复制。
这样叫做 shallow copy 浅复制，a 和 b 在内存中是 share 一个地址。

1
2
ListNode a = new ListNode(0);
ListNode b = a;

这样叫做深度复制，a 和 b 在内存中各自有各自的地址。

1
2
ListNode a = new ListNode(0);
ListNode b = new ListNode(0);

思路一 - hashmap

用 hashmap，key 是每个 node，value 是存每个 node 的 copy。复制完毕之后再遍历一遍，做每个 node 的指针复制。

复杂度

时间O(n)
空间O(n)

代码

Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public Node copyRandomList(Node head) {
        HashMap<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) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}

JavaScript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function(head) {
    if (head === null) return null;
    let map = new Map();
    let cur = head;
    while (cur !== null) {
        map.set(cur, new Node(cur.val, cur.next, cur.random));
        cur = cur.next;
    }
    cur = head;
    while (cur !== null) {
        map.get(cur).next = map.get(cur.next) || null;
        map.get(cur).random = map.get(cur.random) || null;
        cur = cur.next;
    }
    return map.get(head);
};

思路二

另外一种思路是首先复制整个链表，将每一个复制的节点 copy 加到原节点后面。然后将每个 copy node 的 random node 也链接好，再断开原链表和复制的链表。这种做法无需额外空间。

注意因为 random node 其实也是来自于这个链表，跟 next 指针的区别在于 next 指针是指向每个 node 的下一个 node，random 指针是随机指向了整个链表中的某个 node，所以当第一遍复制好了 copy node 之后，也需要把 cur.next.random 指向 cur.random.next，因为

1
2
cur.next.random = copy.random
cur.random.next = 某一个copy node

复杂度

时间O(n)
空间O(1)

代码

Java实现

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
class Solution {
    public Node copyRandomList(Node head) {
        // corner case
        if (head == null) {
            return null;
        }

        // copy all the cur nodes
        Node cur = head;
        while (cur != null) {
            Node next = cur.next;
            Node copy = new Node(cur.val);
            cur.next = copy;
            copy.next = next;
            cur = next;
        }

        // copy all the random nodes
        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                // cur.random.next是某个random节点的copy
                // cur.next.random是当前节点的copy的random指针
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }

        // separate two lists
        cur = head;
        Node dummy = new Node(0);
        Node copyHead = dummy;
        Node copy;
        while (cur != null) {
            Node next = cur.next.next;
            copy = cur.next;
            copyHead.next = copy;
            copyHead = copy;
            cur.next = next;
            cur = next;
        }
        return dummy.next;
    }
}

JavaScript实现

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
/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function (head) {
    // make copy of each node
    let cur = head;
    while (cur) {
        let next = cur.next;
        let copy = new Node(cur.val);
        cur.next = copy;
        copy.next = next;
        cur = next;
    }

    // set random property
    cur = head;
    while (cur) {
        if (cur.random !== null) {
            cur.next.random = cur.random.next;
        }
        cur = cur.next.next;
    }

    // detach copied list
    cur = head;
    let dummyHead = new Node(0);
    let newHead = dummyHead;
    while (cur) {
        let next = cur.next.next;
        // extract the copy
        let copy = cur.next;
        newHead.next = copy;
        newHead = copy;
        // restore the original list
        cur.next = next;
        cur = next;
    }
    return dummyHead.next;
};

最后附上discussion里面一个非常好的图解。

相关题目

1
2
3
4
133. Clone Graph
138. Copy List with Random Pointer
1485. Clone Binary Tree With Random Pointer
1490. Clone N-ary Tree
#leetcode #hashmap #java #javascript #linked list
[LeetCode] 138. Copy List with Random Pointer
https://shurui91.github.io/posts/2629173317.html
Author
Aaron Liu
Posted on
January 18, 2020
Licensed under