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.
Solution:
1. /*
2. * Definition for singly-linked list with a random pointer.
3. * class RandomListNode {
4. * int label;
5. * RandomListNode next, random;
6. * RandomListNode(int x) { this.label = x; }
7. * };
8. /
9. public class Solution {
10. public RandomListNode copyRandomList(RandomListNode head) {
11. if (head == null) return null;
12. 13. Map map = new HashMap();
14. 15. // step 1. copy all the nodes
16. RandomListNode node = head;
17. while (node != null) {
18. map.put(node, new RandomListNode(node.label));
19. node = node.next;
20. }
21. 22. // step 2. assign next and random pointers
23. node = head;
24. while (node != null) {
25. map.get(node).next = map.get(node.next);
26. map.get(node).random = map.get(node.random);
27. node = node.next;
28. }
29. 30. return map.get(head);
31. }
32. }