Leetcode: 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.

Understand the problem:
The crux to understand the problem is the deep copy of the list. If the linked list has only next reference, copying could be quite straight-forward. However, with the existence of random pointer, the new copied linked list has no idea where it should point to, because the node pointed by the random pointer at the old linked list is not the same reference in the new linked list.

Solution:
One straight-forward solution to address this problem is to use a hashed map. The key and value is the old and new node in the linked list. So for the random pointer points to a old node, we can map it to the new node. 

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }
        
        HashMap<RandomListNode, RandomListNode> hashMap = new HashMap<RandomListNode, RandomListNode>();
        
        RandomListNode p = head;
        RandomListNode newHead = new RandomListNode(head.label);
        RandomListNode q = newHead;
        
        hashMap.put(head, newHead);
        p = p.next;
        
        while (p != null) {
            RandomListNode temp = new RandomListNode(p.label);
            q.next = temp;
            q = temp;
            hashMap.put(p, q);
            
            p = p.next;
        }
        
        p = head;
        q = newHead;
        
        while (p != null) {
            if (p.random != null) {
                q.random = hashMap.get(p.random);
            } else {
                q.random = null;
            }
            p = p.next;
            q = q.next;
        }
        
        return newHead;
    }
}

Discussion:
The solution above has time complexity of O(n) since we iterate the linked twice. It has the space complexity O(n) as well since we used a hash map to store the relations between old and new node.

A better approach:
We can solve the problem with only O(1) space complexity. The solution has three steps. 
1. copy the node and insert new nodes into the old node.
2. copy the new random pointer
3. break down the linked list and recover the old linked list

Code (Java):

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }
        
        // step 1: copy node and insert behind
        RandomListNode p = head;
        while (p != null) {
            RandomListNode copy = new RandomListNode(p.label);
            RandomListNode nextNode = p.next;
            p.next = copy;
            copy.next = nextNode;
            p = nextNode;
        }
        
        // step 2: copy random pointers
        p = head;
        while (p != null) {
            RandomListNode nextNode = p.next.next;
            if (p.random != null) {
                p.next.random = p.random.next;
            } else {
                p.next.random = null;
            }
            
            p = nextNode;
        }
        
        // step 3: break down the linked list and recover the original and new linked list
        p = head;
        RandomListNode newHead = p.next;
        
        while (p != null) {
            RandomListNode q = p.next;
            p.next = q.next;
            if (q.next != null) {
                q.next = p.next.next;
            }
            
            p = p.next;
        }
        
        return newHead;
        
    }
}