1+ /*
2+ Author: Andy, nkuwjg@gmail.com
3+ Date: Jan 13, 2015
4+ Problem: Copy List with Random Pointer
5+ Difficulty: Easy
6+ Source: http://oj.leetcode.com/problems/copy-list-with-random-pointer/
7+ Notes:
8+ A linked list is given such that each node contains an additional random pointer
9+ which could point to any node in the list or null.
10+ Return a deep copy of the list.
11+
12+ Solution: 1. HashMap
13+ 2. uses constant extra space.
14+ 3. Recursive. (Stack)-->StackOverflow in Java.
15+ 4. Iterative. (Queue)
16+ */
17+ /**
18+ * Definition for singly-linked list with a random pointer.
19+ * class RandomListNode {
20+ * int label;
21+ * RandomListNode next, random;
22+ * RandomListNode(int x) { this.label = x; }
23+ * };
24+ */
25+ public class Solution {
26+ public RandomListNode copyRandomList_1 (RandomListNode head ) {
27+ if (head ==null )return null ;
28+ HashMap <RandomListNode ,RandomListNode >map =new HashMap <RandomListNode ,RandomListNode >();
29+ RandomListNode dummy =new RandomListNode (-1 );
30+ RandomListNode curNew =dummy ,cur =head ;
31+ while (cur !=null ) {
32+ if (map .containsKey (cur ) ==false ) {
33+ map .put (cur ,new RandomListNode (cur .label ));
34+ }
35+ if (cur .random !=null &&map .containsKey (cur .random ) ==false ) {
36+ map .put (cur .random ,new RandomListNode (cur .random .label ));
37+ }
38+ curNew .next =map .get (cur );
39+ curNew .next .random =map .get (cur .random );
40+ curNew =curNew .next ;
41+ cur =cur .next ;
42+ }
43+ return dummy .next ;
44+ }
45+ public RandomListNode copyRandomList_2 (RandomListNode head ) {
46+ if (head ==null )return null ;
47+ RandomListNode cur =head ;
48+ while (cur !=null ) {
49+ RandomListNode newnode =new RandomListNode (cur .label );
50+ newnode .next =cur .next ;
51+ cur .next =newnode ;
52+ cur =cur .next .next ;
53+ }
54+ cur =head ;
55+ while (cur !=null ) {
56+ if (cur .random !=null ) {
57+ cur .next .random =cur .random .next ;
58+ }
59+ cur =cur .next .next ;
60+ }
61+ RandomListNode dummy =new RandomListNode (-1 );
62+ RandomListNode curNew =dummy ;
63+ cur =head ;
64+ while (cur !=null ) {
65+ curNew .next =cur .next ;
66+ curNew =curNew .next ;
67+ cur .next =cur .next .next ;
68+ cur =cur .next ;
69+ }
70+ return dummy .next ;
71+ }
72+ public RandomListNode copyRandomList_3 (RandomListNode head ) {/*StackOverflowError*/
73+ if (head ==null )return null ;
74+ HashMap <RandomListNode ,RandomListNode >map =new HashMap <RandomListNode ,RandomListNode >();
75+ return copy (head ,map );
76+ }
77+ public RandomListNode copy (RandomListNode root ,HashMap <RandomListNode ,RandomListNode >map ) {
78+ if (root ==null )return null ;
79+ if (map .containsKey (root ) ==true ) {
80+ return map .get (root );
81+ }
82+ RandomListNode newnode =new RandomListNode (root .label );
83+ map .put (root ,newnode );
84+ newnode .next =copy (root .next ,map );
85+ newnode .random =copy (root .random ,map );
86+ return newnode ;
87+ }
88+ public RandomListNode copyRandomList_4 (RandomListNode head ) {
89+ if (head ==null )return null ;
90+ HashMap <RandomListNode ,RandomListNode >map =new HashMap <RandomListNode ,RandomListNode >();
91+ Queue <RandomListNode >queue =new LinkedList <RandomListNode >();
92+ queue .offer (head );
93+ map .put (head ,new RandomListNode (head .label ));
94+ while (queue .isEmpty () ==false ) {
95+ RandomListNode cur =queue .poll ();
96+ if (cur .next !=null &&map .containsKey (cur .next ) ==false ) {
97+ RandomListNode newnode =new RandomListNode (cur .next .label );
98+ map .put (cur .next ,newnode );
99+ queue .offer (cur .next );
100+ }
101+ map .get (cur ).next =map .get (cur .next );
102+ if (cur .random !=null &&map .containsKey (cur .random ) ==false ) {
103+ RandomListNode newnode =new RandomListNode (cur .random .label );
104+ map .put (cur .random ,newnode );
105+ queue .offer (cur .random );
106+ }
107+ map .get (cur ).random =map .get (cur .random );
108+ }
109+ return map .get (head );
110+ }
111+ }
