138 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; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        if (head == null) {
            return head;
        }
        RandomListNode curt = head;
        while (curt != null) {
            map.put(curt, new RandomListNode(curt.label));
            curt = curt.next;
        }
        curt = head;
        while (curt != null) {
            RandomListNode curt_copy = map.get(curt);
            if (curt.next != null) {
                RandomListNode next_copy = map.get(curt.next);
                curt_copy.next = next_copy;
            }
            if (curt.random != null) {
                RandomListNode random_copy = map.get(curt.random);
                curt_copy.random = random_copy;
            }
            curt = curt.next;
        }


        return map.get(head);
    }
}