[LeetCode] Copy List with Random Pointer

Problem:

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:O(n)

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null)
            return null;
        RandomListNode cur = head;
        RandomListNode ret = null;
        RandomListNode pre = null;
        HashMap<RandomListNode,RandomListNode> map = new HashMap<>();
        while(cur!=null){
            RandomListNode newnode = new RandomListNode(cur.label);
            map.put(cur,newnode);
            cur = cur.next;
            if(ret == null){
                ret = newnode;
                pre = newnode;
            }
            else{
                pre.next = newnode;
                pre = pre.next;
            }    
        }
        cur = head;
        pre = ret;
         while(cur!=null){
            pre.random = map.get(cur.random);
            cur = cur.next;
            pre = pre.next;
        }
        return ret;
    }
}