package com.fishercoder.solutions;

import java.util.HashMap;
import java.util.Map;

/**138. 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.
 * */

public class _138 {

    public RandomListNode copyRandomList(RandomListNode head) {
        /**Key is the original nodes, value is the new nodes we're deep copying to.*/
        Map<RandomListNode, RandomListNode> map = new HashMap();
        RandomListNode node = head;

        //loop for the first time: copy the node themselves with only labels
        while (node != null) {
            map.put(node, new RandomListNode(node.label));
            node = node.next;
        }

        //loop for the second time: copy random and next pointers
        node = head;
        while (node != null) {
            map.get(node).next = map.get(node.next);
            map.get(node).random = map.get(node.random);
            node = node.next;
        }

        return map.get(head);
    }

    // Definition for singly-linked list with a random pointer.
    class RandomListNode {
        int label;

        RandomListNode next;
        RandomListNode random;

        RandomListNode(int x) {
            this.label = x;
        }
    }
}

@@ -81,16 +81,20 @@
 ap;%0A%0A/**
+%0A * 
 138. Cop
@@ -323,16 +323,49 @@
  _138 %7B%0A
+  public static class Solution1 %7B
 %0A    pub
@@ -427,18 +427,16 @@
 %7B%0A      
-  
 /**Key i
@@ -505,18 +505,16 @@
 g to.*/%0A
-  
       Ma
@@ -566,34 +566,32 @@
 ashMap();%0A      
-  
 RandomListNode n
@@ -603,18 +603,16 @@
  head;%0A%0A
-  
       //
@@ -680,26 +680,24 @@
 abels%0A      
-  
 while (node 
@@ -699,36 +699,32 @@
 node != null) %7B%0A
-    
         map.put(
@@ -762,36 +762,32 @@
 abel));%0A        
- 
-   
 node = node.next
@@ -790,31 +790,27 @@
 next;%0A      
-  
 %7D%0A%0A
-  
       //loop
@@ -863,26 +863,24 @@
 nters%0A      
- 
- 
 node = head;
@@ -880,18 +880,16 @@
 = head;%0A
-  
       wh
@@ -905,28 +905,24 @@
  != null) %7B%0A
-    
         map.
@@ -962,28 +962,24 @@
 t);%0A        
-    
 map.get(node
@@ -1015,28 +1015,24 @@
 m);%0A        
-    
 node = node.
@@ -1039,31 +1039,27 @@
 next;%0A      
-  
 %7D%0A%0A
-  
       return
@@ -1178,18 +1178,16 @@
 %7B%0A      
-  
 int labe
@@ -1188,34 +1188,32 @@
 t label;%0A%0A      
- 
- 
 RandomListNode n
@@ -1213,26 +1213,24 @@
 tNode next;%0A
-  
       Random
@@ -1249,26 +1249,24 @@
 dom;%0A%0A      
- 
- 
 RandomListNo
@@ -1285,20 +1285,16 @@
         
-   
- 
 this.lab
@@ -1309,16 +1309,18 @@
     
+  %7D%0A
     %7D%0A
-  
   %7D%0A

refactor 138