138. Copy List with Random Pointer.md

138. 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.

Solution

• Java

  • mine

    Runtime: 0 ms, faster than 100.00%, Memory Usage: 39 MB, less than 5.61% of Java online submissions

    //O(N)time O(N)space
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        HashMap<Node, Node> map = new HashMap<>();
    
        //copy the nodes
        Node node = head;
        while (node != null) {
            map.put(node, new Node(node.val));
            node = node.next;
        }
    
        //set map value's next and random  with map key 
        node = head;
        while (node != null) {
            map.get(node).next = map.get(node.next);
            map.get(node).random = map.get(node.random);
            node = node.next;
        }
    
        return map.get(head);
    }
    

  • the most votes

    Runtime: 0 ms, faster than 100.00%, Memory Usage: 39.2 MB, less than 5.61% of Java online submissions

    //O(N)time O(N)space
    public Node copyRandomList(Node head) {
        Node iter = head, next;
    
        // First round: make copy of each node,
        // and link them together side-by-side in a single list.
        while (iter != null) {
            next = iter.next;
    
            Node copy = new Node(iter.val);
            iter.next = copy;
            copy.next = next;
    
            iter = next;
        }
    
        // Second round: assign random pointers for the copy nodes.
        iter = head;
        while (iter != null) {
            if (iter.random != null) {
                iter.next.random = iter.random.next;
            }
            iter = iter.next.next;
        }
    
        // Third round: restore the original list, and extract the copy list.
        iter = head;
        Node pseudoHead = new Node(0);
        Node copy, copyIter = pseudoHead;
    
        while (iter != null) {
            next = iter.next.next;
    
            // extract the copy
            copy = iter.next;
            copyIter.next = copy;
            copyIter = copy;
    
            // restore the original list
            iter.next = next;
    
            iter = next;
        }
    
        return pseudoHead.next;
    }