Copy List with Random Pointer

Description

https://leetcode.com/problems/copy-list-with-random-pointer/description/

Solution

The key point is to mantain a mapping from old node to copied node,

Step1: traverse the list to form the linked list

Step2: traverse the list to complete the random point relationship(using map)

/**
 * 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> oldToNew = new HashMap<>();
        RandomListNode ret = new RandomListNode(head.label);
        //traverse the list
        RandomListNode traverseOld = head, traverseNew = ret;
        while(traverseOld != null) {
            oldToNew.put(traverseOld, traverseNew);
            if(traverseOld.next != null) {
                traverseNew.next = new RandomListNode(traverseOld.next.label);
            }else {
                traverseNew.next = null;
            }
            traverseOld = traverseOld.next;
            traverseNew = traverseNew.next;
        }
        
        //Handle the random point
        traverseNew = ret;
        traverseOld = head;
        while(traverseNew != null) {
            traverseNew.random = oldToNew.get(traverseOld.random);
            traverseNew = traverseNew.next;
            traverseOld = traverseOld.next;
        }
        
        return ret;
    }
}