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 static class Solution1 {
    public Node copyRandomList(Node head) {
      /**Key is the original nodes, value is the new nodes we're deep copying to.*/
      Map<Node, Node> map = new HashMap();
      Node node = head;

      //loop for the first time: copy the node themselves with only labels
      while (node != null) {
        map.put(node, new Node(node.val));
        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 Node {
      int val;

      Node next;
      Node random;

      Node(int x) {
        this.val = x;
      }
    }
  }
}

@@ -122,16 +122,17 @@
 inter%0A *
+ 
 %0A * A li
@@ -297,18 +297,16 @@
 e list.%0A
- *
  */%0A%0Apub
@@ -322,16 +322,18 @@
  _138 %7B%0A
+  
   public
@@ -358,16 +358,20 @@
 tion1 %7B%0A
+    
     publ
@@ -412,16 +412,22 @@
 %7B%0A      
+     
+ 
 /**Key i
@@ -496,16 +496,22 @@
 g to.*/%0A
+      
       Ma
@@ -547,24 +547,30 @@
 ap();%0A      
+   
+   
 Node node = 
@@ -576,16 +576,22 @@
  head;%0A%0A
+      
       //
@@ -657,16 +657,22 @@
  labels%0A
+      
       wh
@@ -696,24 +696,32 @@
 ) %7B%0A        
+      
+  
 map.put(node
@@ -743,16 +743,24 @@
 .val));%0A
+        
         
@@ -783,25 +783,37 @@
 ;%0A      
+ 
-%7D%0A%0A
+     %7D%0A%0A     
       
+ 
 //loop f
@@ -862,16 +862,22 @@
 ointers%0A
+      
       no
@@ -889,24 +889,30 @@
 head;%0A      
+    
+  
 while (node 
@@ -914,32 +914,40 @@
 node != null) %7B%0A
+        
         map.get(
@@ -979,16 +979,24 @@
 .next);%0A
+        
         
@@ -1040,16 +1040,24 @@
 andom);%0A
+        
         
@@ -1076,27 +1076,39 @@
 next;%0A      
+     
+ 
 %7D%0A%0A
+      
       return
@@ -1123,23 +1123,31 @@
 (head);%0A
+    
     %7D%0A%0A
+    
     // D
@@ -1202,16 +1202,20 @@
 ointer.%0A
+    
     clas
@@ -1229,16 +1229,22 @@
 %7B%0A      
+  
+    
 int val;
@@ -1247,24 +1247,30 @@
 val;%0A%0A      
+  
+    
 Node next;%0A 
@@ -1270,24 +1270,30 @@
 next;%0A      
+ 
+     
 Node random;
@@ -1296,24 +1296,30 @@
 dom;%0A%0A      
+     
+ 
 Node(int x) 
@@ -1328,16 +1328,24 @@
         
+     
+   
 this.val
@@ -1360,16 +1360,28 @@
     
+  
+    
 %7D%0A    
+ 
-%7D%0A
+   %7D%0A  
   %7D%0A

refactor 138