package com.coderevisited.linkedlists.doubly;

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;

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)
    {
        //Save key -> newly created Node
        Map<Integer, DoublyLinkedListNode> prev = new HashMap<>();
        //Save given list head
        DoublyLinkedListNode origHead = head;
        //start building the new list with next pointers, at each step save the newly created node
        DoublyLinkedListNode newHead = null;
        if (head != null) {
            newHead = new DoublyLinkedListNode(head.getValue(), null, null);
            prev.put(newHead.getValue(), newHead);
            head = head.getNext();
        }

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

        //Now traverse the original list, get the key of prev node and look in the map for corresponding new Node
        //update previous
        temp = newHead;
        while (origHead != null) {
            DoublyLinkedListNode prevNode = prev.get(origHead.getPrev().getValue());
            temp.setPrev(prevNode);
            origHead = origHead.getNext();
            temp = temp.getNext();
        }


        return newHead;
    }

}

@@ -507,16 +507,33 @@
 copyList
+WithoutExtraSpace
 (head);%0A
@@ -1949,16 +1949,1200 @@
       %7D%0A
+        return newHead;%0A    %7D%0A%0A%0A    private static DoublyLinkedListNode copyListWithoutExtraSpace(DoublyLinkedListNode head)%0A    %7B%0A        DoublyLinkedListNode temp = head;%0A        //1. Insert a duplicate node next to each node in the original list%0A        while (temp != null) %7B%0A            DoublyLinkedListNode node = new DoublyLinkedListNode(temp.getValue(), null, temp.getNext());%0A            temp.setNext(node);%0A            temp = node.getNext();%0A        %7D%0A%0A        temp = head;%0A        //2. set the previous pointer to all created nodes%0A        while (temp != null) %7B%0A            temp.getNext().setPrev(temp.getPrev().getNext());%0A            temp = temp.getNext().getNext();%0A        %7D%0A%0A        //3. restore next pointers%0A        DoublyLinkedListNode newHead = head.getNext();%0A        temp = head;%0A        DoublyLinkedListNode copy = newHead;%0A        while (temp != null) %7B%0A            temp.setNext(temp.getNext().getNext());%0A            if (copy.getNext() == null) %7B%0A                copy.setNext(null);%0A            %7D else %7B%0A                copy.setNext(copy.getNext().getNext());%0A                copy = copy.getNext();%0A            %7D%0A            temp = temp.getNext();%0A        %7D%0A
 %0A%0A      
@@ -3155,21 +3155,22 @@
 rn newHead;%0A
+%0A
     %7D%0A%0A%7D%0A

Copy double linked list with arbitrary pointers