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 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;
      }
    }
  }
}

@@ -368,26 +368,16 @@
  public 
-RandomList
 Node cop
@@ -388,26 +388,16 @@
 domList(
-RandomList
 Node hea
@@ -499,34 +499,14 @@
 Map%3C
-RandomListNode, RandomList
+Node, 
 Node
@@ -530,34 +530,24 @@
 ap();%0A      
-RandomList
 Node node = 
@@ -683,26 +683,16 @@
 de, new 
-RandomList
 Node(nod
@@ -693,20 +693,18 @@
 de(node.
-labe
+va
 l));%0A   
@@ -1093,26 +1093,16 @@
   class 
-RandomList
 Node %7B%0A 
@@ -1110,20 +1110,18 @@
     int 
-labe
+va
 l;%0A%0A    
@@ -1118,34 +1118,24 @@
 val;%0A%0A      
-RandomList
 Node next;%0A 
@@ -1135,34 +1135,24 @@
 next;%0A      
-RandomList
 Node random;
@@ -1159,26 +1159,16 @@
 %0A%0A      
-RandomList
 Node(int
@@ -1186,20 +1186,18 @@
    this.
-labe
+va
 l = x;%0A 

refactor 138