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.

HashMap is always a good helper for this kind of clone problem. Make copy and then rearrange pointers! just as I did in work. There might be better way to do it, but this one is rooted in heart and always work!

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

/** * 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 { /** * @param head: The head of linked list with a random pointer. * @return: A new head of a deep copy of the list. */ public RandomListNode copyRandomList(RandomListNode head) { // write your code here //use hashmap to help if(head==null)return null; RandomListNode p = head,cloneHead=null; Map<RandomListNode,RandomListNode> map = new HashMap<RandomListNode,RandomListNode>(); while(p!=null){ map.put(p,new RandomListNode(p.label)); p=p.next; } for(Map.Entry<RandomListNode,RandomListNode> e:map.entrySet()){ if(e.getKey()==head){ cloneHead = e.getValue(); } if(e.getKey().next==null) e.getValue().next=null; else e.getValue().next = map.get(e.getKey().next); if(e.getKey().random==null) e.getValue().random=null; else e.getValue().random = map.get(e.getKey().random); } return cloneHead; } }