Copy List With Random Pointers

Problem Description

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.

Note that, the RandomListNode is defined as below;

class RandomListNode {
    int label;
    RandomListNode next, random;
    RandomListNode(int x) { this.label = x; }
}

Solution 1: Using recursion

public class Solution {

    public HashMap<RandomListNode, RandomListNode> createdNode; 
    public RandomListNode copyRandomList(RandomListNode head) {
        createdNode = new HashMap<RandomListNode, RandomListNode>();
        return cc(head);
    }
    
    private RandomListNode cc(RandomListNode node) {
        if(node == null)
        {
            return null;
        }
    
        RandomListNode newNode = new RandomListNode(node.label);
    
        createdNode.put(node, newNode);        
        newNode.next = cc(node.next);
       
        //now assign the random pointer
        RandomListNode newRandom = null;
        if(node.random != null)
        {
            newRandom = createdNode.get(node.random);
        }
        newNode.random = newRandom;
    
        return newNode;    
    }
}

Solution 2: Using O(n) space

public class Solution{
    
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null) return null;
        java.util.HashMap<RandomListNode, RandomListNode> map = new java.util.HashMap<RandomListNode, RandomListNode>();
        RandomListNode copiedHead = new RandomListNode(head.label);
        map.put(head, copiedHead);
        
        for(RandomListNode cur = head.next, cpLst = copiedHead; cur != null; cur = cur.next, cpLst = cpLst.next){
            cpLst.next = new RandomListNode(cur.label);
            map.put(cur, cpLst.next);
        }
        for(RandomListNode cur = head, cpCur = copiedHead; cur != null; cur = cur.next, cpCur = cpCur.next)
            cpCur.random = cur.random == null ? null : map.get(cur.random);
        return copiedHead;
    }
} 

Solution 3: Using O(1) space

In this solution, we don't use the HashMap in the Solution 2.
Suppose that initially we have this RandomList

Without the random pointers, we can copy the list easily. With the random pointers, we don't want to use the hash map, so there must be a way to keep track of information when make a new list. Let's see in the following image

After making such changes, we iterate through the copied list again, assign random pointers, then recover the pointers in the initiali RandomList! And here is the code.

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null) return null;
        
        RandomListNode i = head, n, t;
        
        while (i != null) {
            n = i.next;
            RandomListNode copy = new RandomListNode(i.label);
            
            i.next = copy;
            copy.next = n;
            i = n;
        }
    
        //now assign random pointers
        i = head; 
        while(i!=null){
            if(i.random!=null)
                i.next.random = i.random.next;
            i = i.next.next;
        }
        
        //now recover the original structure
        i = head; n = i.next;
        RandomListNode foo = n;
        while(i!=null){
            i.next = n.next;
            i = i.next;
            n.next = i==null?null:i.next;
            n = n.next;
        }
        return foo;
    }
}