Copy List with Random Pointer | Leetcode

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.

---

Solution: Iterate through the list from beginning to end, creating a clone node for each node in the list. Put all these clone nodes in a hashmap.

Iterate through the list again, this time linking up the next and random pointers of all the clone nodes.

Return the clone node of the head node as the answer.

/**
 * 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;
        
        Map<Integer, RandomListNode> map = new HashMap<>();
        RandomListNode cur = head;
        do {
            map.put(cur.label, new RandomListNode(cur.label));
            cur = cur.next;
        } while (cur != null);
        
        cur = head;
        do {
            RandomListNode node = map.get(cur.label);
            if (cur.next != null) {
                node.next = map.get(cur.next.label);
            }
            if (cur.random != null) {
                node.random = map.get(cur.random.label);
            }
            cur = cur.next;
        } while (cur != null);
        
        return map.get(head.label);
    }
}