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.

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */

/*
Use hashmap to implement deep copy.
time:O(n),  space:O(n)
*/

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }
        Map<RandomListNode, RandomListNode> map = copyNode(head);
        copyRandom(head, map);
        return map.get(head);
    }
    public Map<RandomListNode, RandomListNode> copyNode                                                       (RandomListNode head) {
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode dummy = new RandomListNode(-1);
        RandomListNode tail = dummy;
        while (head != null) {
            map.put(head, new RandomListNode(head.label));
            tail.next = map.get(head);
            tail = tail.next;
            head = head.next;
        }
        return map;
    }
    public void copyRandom(RandomListNode head, 
                      Map<RandomListNode, RandomListNode> map) {
        while (head != null) {
            if (head.random == null) {
                map.get(head).random = null;
            } else {
                map.get(head).random = map.get(head.random);
            }
            head = head.next;
        }
    }
}


/*
Use constant space to implement deep copy.
1 -> 1 -> 2 -> 2 -> null, deep copy each node and follow the original node.

time:O(n),  space:O(1)
*/

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }      
        copyNode(head);
        copyRandom(head);
        return copyNext(head);
       
    }
    public void copyNode(RandomListNode head) {
        while (head != null) {
            RandomListNode tmp = new RandomListNode(head.label);
            tmp.next = head.next;
            head.next = tmp;
            head = tmp.next;
        }
    }
    public void copyRandom(RandomListNode head) {
        while (head != null) {
            if (head.random == null) {
                head.next.random = null;
            } else {
                head.next.random = head.random.next;
            }
            head = head.next.next;
        }
    }
    public RandomListNode copyNext(RandomListNode head) {
        RandomListNode dummy = new RandomListNode(0);
        RandomListNode tail = dummy;
        while (head != null) {
            tail.next = head.next;
            tail = tail.next;
            head.next = tail.next;
            head = head.next;
        }
        return dummy.next;
    }
}