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.

思路

遍历list将所有节点new一个出来放到hashmap中，第二遍遍历list将旧的节点对应新节点取出来组成链表就okay了

 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 import java.util.HashMap;
10 import java.util.Map;
11 
12 public class Solution {
13     public RandomListNode copyRandomList(RandomListNode head) {
14         if(head == null)
15             return head;
16         Map<RandomListNode, RandomListNode> old2new = new HashMap<RandomListNode, RandomListNode>();
17         
18         //新的头结点
19         RandomListNode newHead = new RandomListNode(head.label);
20         old2new.put(head, newHead);
21         
22         RandomListNode tempHead = head.next;                                    //所有的节点放到hashmap中
23         while(tempHead != null){
24             RandomListNode tempNode = new RandomListNode(tempHead.label);
25             old2new.put(tempHead, tempNode);
26             tempHead = tempHead.next;
27         }//while
28         
29         RandomListNode tempNewHead = null;
30         tempHead = head;
31         
32         while(tempHead != null){
33             tempNewHead = old2new.get(tempHead);
34             tempNewHead.next = old2new.get(tempHead.next);
35             tempNewHead.random = old2new.get(tempHead.random);
36             tempHead = tempHead.next;
37             tempNewHead = tempNewHead.next;
38         }//while
39         
40         return newHead;
41     }
42 }