CloneDoubleLinkedList.java

import java.util.Hashtable;
public class CloneDoubleLinkedList{
    private class Node{
        private String item;
        private Node next;
        private Node random;
    }
    
    public Node cloneListClever(Node first){
        Node current = first;
        Node cloneHead = null;
        Node cloneCurrent = null;
        
        while (current != null){
            Node temp = current.clone();
            if (cloneHead == null){
                cloneHead = temp;
            }
            cloneCurrent = temp;
            
            // inserting the cloneCurrent right after current
            // we do not need to do cloneCurrent.next = current.next 
            // why? Because it's a clone! The reference points to the same place!
            current.next = cloneCurrent;
            current = cloneCurrent.next; // move the pointer
        }
        // reset the pointer since we need a second pass through the list
        current = first;
        cloneCurrent = cloneHead;
        
        while(current != null){
            Node rand = current.random;
            cloneCurrent.random = rand.next; // whatever node rand is pointing to, in the clone, we need rand.next.
            
            // we can separate the two list here;
            current.next = cloneCurrent.next;
            cloneCurrent.next = current.next;
            
            // move to the next nodes in both lists
            current = current.next;
            cloneCurrent = cloneCurrent.next;
        }
        
        return cloneHead;
    }
    
    public Node cloneList(Node first){
        if (first == null) return null;
        
        Node current = first;
        Node cloned = null;
        Node clonedHead = null;
        
        // create a hashtable to save the node and its ind in the original list as key-value pairs.
        Hashtable<Node, Integer> table = new Hashtable<Node, Integer>();
        int count = 0;
        
        while (current != null){
            Node temp = current.clone(); // clone each node
            if (cloned == null){ // if the cloned list is empty
                cloned = temp;
                clonedHead = temp;
            }else{ // if the cloned list is not empty
                cloned.next = temp;
                cloned = cloned.next;
            }
            table.put(current, count); // save the index in the hashtable
            current = current.next; // move the pointer
            count++; // increase the counter
        }
        cloned = clonedHead;
        current = first;
        
        Node[] nodes = new Node[count]; // create an array to save the cloned nodes
        for (int j = 0; j < count; j++){
            nodes[j] = cloned;
            cloned = cloned.next;
        }
        
        int i = 0;
        while(current != null){ // for each node in the original list, check the index of its random node
            Node rand = current.random;
            int ind = table.get(rand);
            nodes[i].random = nodes[ind]; // then wir up the nodes in the cloned list
            i++;
            current = current.next; // move the pointers
        }
        nodes = null;
        return cloneHead;
    }
}