Given a Linked List with random pointers, can you do a deep copy of the list?

The idea is to use a HashMap to store the nodes. The key will be the current node and the value will be our new node. If the current node has random node, then we set the random node for our new node as well. Let's see the solution:

    public Node copyRandomList(Node head) {

        if(head == null){
            return head;
        }
        
        Map<Node, Node> map = new HashMap<>();
        Node dummy = new Node(0);
        Node pre = dummy; 
        Node newNode = null;
        
        while(head != null){
            
            if(map.containsKey(head)){
                newNode = map.get(head);
            } else{
                newNode = new Node(head.val);
                map.put(head, newNode);
            }
            pre.next = newNode;
            
            if(head.random != null){
                if(map.containsKey(head.random)){
                    newNode.random = map.get(head.random);
                } else{
                    newNode.random = new Node(head.random.val);
                    map.put(head.random, newNode.random);
                }
            }
            pre = newNode;
            head = head.next;
        }
        return dummy.next; 
    }

Using hash map will allocate O(n) space, but can we do it without allocating new space?

The second solution (without hash map) works like this:

1. transform list 1->2->3-4 into 1->1'->2->2'->3->3'->4->4'
2. copy random node, ex: 1ʳᵃⁿᵈ->5 to 1ʳᵃⁿᵈ'->5'
3. modify list to return the new copied list only

Here's the solution:

    public Node copyRandomList(Node head) {
        if(head == null){
            return head;
        }
        
        Node node = head;
        
        // 1. copy node and add in between current and next node
        while(node != null){  
            Node newNode = new Node(node.val);
            newNode.random = node.random;
            newNode.next = node.next;
            node.next = newNode;
            node = node.next.next;    
        }
        
        // reset to head
        node = head;
        
        // 2. copy random node
        while(node != null){
            if(node.random != null){
                node.next.random = node.random.next;
            }   
            node = node.next.next;
        }
        
        Node dummy = new Node(0);
        Node prev = dummy;
        // reset to head
        node = head;
        
        // 3. split the list into original and copied list 
        while(node != null){
            Node newNode = node.next;
            node.next = newNode.next;
            prev.next = newNode;
            prev = newNode;
            node = node.next;
        }
        
        return dummy.next;
    }

Here's visual graph for understanding:

Note | If your newly allocated space is not your input or output, then you are not allocating new extra space.

---

That's all! Thanks for reading!

Post was published on 2 Feb 2020, last updated on 2 Feb 2020.

Like the content? Support the author by paypal.me!