package com.coderevisited.linkedlists.doubly;

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;

public class CopyDLLWithNextAndArbitrary
{

    public static void main(String[] args)
    {
        PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        DoublyLinkedListNode head = DoublyLinkedList.buildDLLWithArbitraryPointers();
        DoublyLinkedListNode newHead = copyList(head);
        DoublyLinkedList.printList(newHead, pw);
        pw.close();

    }

    private static DoublyLinkedListNode copyList(DoublyLinkedListNode head)
    {
        // Map<Integer, DoublyLinkedListNode> prev = new HashMap<>();
        DoublyLinkedListNode newHead = null;
        if (head != null) {
            newHead = new DoublyLinkedListNode(head.getValue(), null, null);
            //  prev.put(head.getPrev().getValue(), null);
            head = head.getNext();
        }

        DoublyLinkedListNode temp = newHead;
        while (head != null) {
            DoublyLinkedListNode node = new DoublyLinkedListNode(head.getValue(), null, null);
            temp.setNext(node);
            temp = node;
            //  prev.put(head.getPrev().getValue(), null);
            head = head.getNext();

        }


        return newHead;
    }

}

@@ -133,16 +133,64 @@
 tWriter;
+%0Aimport java.util.HashMap;%0Aimport java.util.Map;
 %0A%0Apublic
@@ -684,16 +684,54 @@
       //
+Save key -%3E newly created Node%0A       
  Map%3CInt
@@ -778,24 +778,200 @@
 ashMap%3C%3E();%0A
+        //Save given list head%0A        DoublyLinkedListNode origHead = head;%0A        //start building the new list with next pointers, at each step save the newly created node%0A
         Doub
@@ -1110,36 +1110,32 @@
 ull);%0A          
-  //
   prev.put(head.
@@ -1125,39 +1125,32 @@
    prev.put(
-h
+newH
 ead.
-getPrev().
 getValue(), 
@@ -1142,35 +1142,38 @@
 ad.getValue(), n
-ull
+ewHead
 );%0A            h
@@ -1368,32 +1368,77 @@
 ), null, null);%0A
+            prev.put(node.getValue(), node);%0A
             temp
@@ -1494,52 +1494,359 @@
     
-//  prev.put(head.getPrev().getValue(), null
+head = head.getNext();%0A        %7D%0A%0A        //Now traverse the original list, get the key of prev node and look in the map for corresponding new Node%0A        //update previous%0A        temp = newHead;%0A        while (origHead != null) %7B%0A            DoublyLinkedListNode prevNode = prev.get(origHead.getPrev().getValue());%0A            temp.setPrev(prevNode
 );%0A 
@@ -1852,32 +1852,40 @@
             
-h
+origH
 ead = 
-h
+origH
 ead.getNext(
@@ -1883,24 +1883,58 @@
 .getNext();%0A
+            temp = temp.getNext();
 %0A        %7D%0A%0A

Copy double linked list with arbitrary pointers