Clone a LinkedList with each node having a next and a random pointer

Question

The LinkedList nodes can be 1-->2-->3-->4, where --> indicates next. For their random pointers: 1--> 2, 2--> 4 3-->2 4--1. There can be duplicate data values of the nodes. I'm looking to see if the solution can be improved upon.

class Node
{
int data;//Node data
Node next, random;//Next and random reference
//Node constructor
public Node(int data)
{
 this.data = data;
 this.next = this.random = null;
}
}
// linked list class
class LinkedList
{
Node head;//Linked list head reference
// Linked list constructor
public LinkedList(Node head)
{
 this.head = head;
}
// push method to put data always at the head
// in the linked list.
public void push(int data)
{
 Node node = new Node(data);
 node.next = this.head;
 this.head = node;
}
// Method to print the list.
void print()
{
 Node temp = head;
 while (temp != null)
 {
 Node random = temp.random;
 int randomData = (random != null)? random.data: -1;
 System.out.println("Data = " + temp.data +
 ", Random data = "+ randomData);
 temp = temp.next;
 }
 }
// Actual clone method which returns head
// reference of cloned linked list.
public LinkedList clone()
{
 // Initialize two references, one with original
 // list's head.
 Node origCurr = this.head, cloneCurr = null;
 // Hash map which contains node to node mapping of
 // original and clone linked list.
 Map<Node, Node> map = new HashMap<Node, Node>();
 // Traverse the original list to help copy into the HashMap
 while (origCurr != null) {
 cloneCurr = new Node(origCurr.data);
 cloneCurr.next = origCurr.next;
 cloneCurr.random = origCurr.random;
 map.put(origCurr, cloneCurr);
 origCurr = origCurr.next;
 }
 //return the head reference of the clone list.
 return new LinkedList(map.get(this.head));
}
}
public class Clone
{
public static void main(String[] args)
{
 // Pushing data in the linked list.
 LinkedList list = new LinkedList(new Node(5));
 list.push(4);
 list.push(3);
 list.push(2);
 list.push(1);
 list.head.random = list.head.next.next;
 list.head.next.random =
 list.head.next.next.next;
 list.head.next.next.random =
 list.head.next.next.next.next;
 list.head.next.next.next.random =
 list.head.next.next.next.next.next;
 list.head.next.next.next.next.random =
 list.head.next;
 // Making a clone of the original linked list.
 LinkedList clone = list.clone();
 // Print the original and cloned linked list.
 System.out.println("Original linked list");
 list.print();
 System.out.println("\nCloned linked list");
 clone.print();
}
}

Answer 1

Not a clone

Your "clone" is not a clone of the original list. It is a single head node that points to the second node of the original list. In order to make a real clone, all pointers in the cloned list should point only to other nodes in the cloned list.

Two passes

Your attempt isn't completely wrong. After creating all the cloned nodes, you just need a second pass where you convert the original node pointers to cloned node pointers using the map you created.