package com.geeksforgeeks.LinkedList;

/**
 * Created by Vaidehi Murarka on 2/5/2017.
 * http://www.geeksforgeeks.org/a-linked-list-with-next-and-arbit-pointer/
 */
public class CloneLLWithArbitraryPointer<T> {
    public LLNode<T> cloneLL(LLNode<T> head){
        if(head == null) return null;
        LLNode<T> result = null, temp = head;
        while(temp != null){
            LLNode<T> clonedNode = new LLNode<T>();
            clonedNode.setData(temp.getData());
            clonedNode.setNext(temp.getNext());
            temp.setNext(clonedNode);
            temp = clonedNode.getNext();
        }

        temp = head;
        while(temp != null){
            temp.getNext().setArbitrary(temp.getArbitrary().getNext());
            temp = temp.getNext().getNext();
        }

        result = head.getNext();
        temp = head;
        while(temp != null){
            temp.setNext(temp.getNext().getNext());
            temp = temp.getNext();
        }

        return result;
    }

    public static void main(String[] args){
        LLNode<Integer> ll1 = new LLNode<>();
        ll1.setData(1);
        LLNode<Integer> ll2 = new LLNode<>();
        ll2.setData(2);

        ll1.setNext(ll2);

        LLNode<Integer> ll3 = new LLNode<>();
        ll3.setData(3);

        ll2.setNext(ll3);

        LLNode<Integer> ll4 = new LLNode<>();
        ll4.setData(4);

        ll3.setNext(ll4);
        ll1.setArbitrary(ll4);
        ll2.setArbitrary(ll1);
        ll3.setArbitrary(ll2);
        ll4.setArbitrary(ll3);
        CloneLLWithArbitraryPointer<Integer> clone = new CloneLLWithArbitraryPointer<>();
         LLNode<Integer> result = clone.cloneLL(ll1);
         while (result!=null){
             System.out.println(result.getData());
             result = result.getNext();
         }
    }
}
