138. Copy List with Random Pointer

Leetcode

https://leetcode.com/problems/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:

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]]

解答

• 方法一

創建一個額外的 newNode 複製原本 oldNode 裡的所有資料

/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */
 var copyRandomList = function(head) {
    if(!head) return null;
    
    // 紀錄 oldNode -> newNode 的對照關係
    const hashmap = new Map();
    const getCloneNode = (node) => {
        if(!node) return null;
        if(hashmap.has(node)) return hashmap.get(node);
        else {
            // 初始化新的 node
            hashmap.set(node, new Node(node.val, null, null))
            return hashmap.get(node);
        }
    }
    
    let oldNode = head;
    let newNode = new Node(oldNode.val);
    hashmap.set(oldNode, newNode);
    
    while(oldNode !== null) {
        newNode.next = getCloneNode(oldNode.next);
        newNode.random = getCloneNode(oldNode.random)
        
        oldNode = oldNode.next;
        newNode = newNode.next;
    }
    
    return hashmap.get(head);
};

Runtime: 76 ms, faster than 70.86% of JavaScript online submissions for Copy List with Random Pointer.

Memory Usage: 40.7 MB, less than 11.89% of JavaScript online submissions for Copy List with Random Pointer.

Time Complexity : O(N)

Space Complexity : O(N) -> hashmap

• 方法二

創建一個 linked list，使得原本的 A -> B -> C 變成 A -> A' -> B -> B' -> C -> C'，再取得 A' -> B' -> C' 極為答案

For example:

A -> B -> C

1. 先 copy 所有 node 的 val，並使其指向變成 A -> A' -> B -> B' -> C -> C'

2. 校正 A' B' C' 的 random 指向

3. 恢復讓 head 變成 A -> B -> C，以及回傳新的 linked list A' -> B' -> C'

var copyRandomList = function(head) {
    if(!head) return null;
    
    let pointer = head;
    // 1. 
    // make original list A -> B -> C
    // to A -> A' -> B -> B' -> C -> C'
    while(pointer) {
        let newNode = new Node(pointer.val, null, null);
        newNode.next = pointer.next;
        pointer.next = newNode;
        pointer = newNode.next;
    }
    
    pointer = head;
    // 2.
    // make cloned node point to correct random
    while(pointer) {
        pointer.next.random = pointer.random !== null ? pointer.random.next : null;
        pointer = pointer.next.next;
    }
    
    // 3.
    // 此時 head 為 A -> A' -> B -> B' -> C -> C'
    // 要將 head 變回原本的 A -> B -> C
    // 並且回傳 A' -> B' -> C'
    let ptr_old_list = head; // A -> B -> C
    let ptr_new_list = head.next; // A' -> B' -> C'
    const head_old = head.next;
    while(ptr_old_list) {
        // 將 head 變回原本的 A -> B -> C
        ptr_old_list.next = ptr_old_list.next.next;
        ptr_old_list = ptr_old_list.next;
        
        // 產出 A' -> B' -> C'
        ptr_new_list.next = ptr_new_list.next ? ptr_new_list.next.next : null;
        ptr_new_list = ptr_new_list.next;
    }
    
    return head_old;
};

Runtime: 87 ms, faster than 21.46% of JavaScript online submissions for Copy List with Random Pointer.

Memory Usage: 40.1 MB, less than 88.71% of JavaScript online submissions for Copy List with Random Pointer.

Time Complexity : O(N)

Space Complexity : O(1)