fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6. // Java program to clone a linked list with random pointers
  7. import java.util.HashMap;
  8. import java.util.Map;
  9.  
  10. // Linked List Node class
  11. class Node
  12. {
  13.     int data;//Node data
  14.     Node next, random;//Next and random reference
  15.  
  16.     //Node constructor
  17.     public Node(int data)
  18.     {
  19.         this.data = data;
  20.         this.next = this.random = null;
  21.     }
  22. }
  23.  
  24. // linked list class
  25. class LinkedList
  26. {
  27.     Node head;//Linked list head reference
  28.  
  29.     // Linked list constructor
  30.     public LinkedList(Node head)
  31.     {
  32.         this.head = head;
  33.     }
  34.  
  35.     // push method to put data always at the head
  36.     // in the linked list.
  37.     public void push(int data)
  38.     {
  39.         Node node = new Node(data);
  40.         node.next = this.head;
  41.         this.head = node;
  42.     }
  43.  
  44.     // Method to print the list.
  45.     void print()
  46.     {
  47.         Node temp = head;
  48.         while (temp != null)
  49.         {
  50.             Node random = temp.random;
  51.             int randomData = (random != null)? random.data: -1;
  52.             System.out.println("Data = " + temp.data +
  53.                                ", Random data = "+ randomData);
  54.             temp = temp.next;
  55.         }
  56.     }
  57.  
  58.     // Actual clone method which returns head
  59.     // reference of cloned linked list.
  60.     public LinkedList clone()
  61.     {
  62.         // Initialize two references, one with original
  63.         // list's head.
  64.         Node origCurr = this.head, cloneCurr = null;
  65.  
  66.         // Hash map which contains node to node mapping of
  67.         // original and clone linked list.
  68.         Map<Node, Node> map = new HashMap<Node, Node>();
  69.  
  70.         // Traverse the original list and make a copy of that
  71.         // in the clone linked list.
  72.         while (origCurr != null)
  73.         {
  74.             cloneCurr = new Node(origCurr.data);
  75.             map.put(origCurr, cloneCurr);
  76.             origCurr = origCurr.next;
  77.         }
  78.  
  79.         // Adjusting the original list reference again.
  80.         origCurr = this.head;
  81.  
  82.         // Traversal of original list again to adjust the next
  83.         // and random references of clone list using hash map.
  84.         while (origCurr != null)
  85.         {
  86.             cloneCurr = map.get(origCurr);
  87.             cloneCurr.next = map.get(origCurr.next);
  88.             cloneCurr.random = map.get(origCurr.random);
  89.             origCurr = origCurr.next;
  90.         }
  91.  
  92.         //return the head reference of the clone list.
  93.         return new LinkedList(map.get(this.head));
  94.     }
  95. }
  96.  
  97. // Driver Class
  98. class Main
  99. {
  100.     // Main method.
  101.     public static void main(String[] args)
  102.     {
  103.         // Pushing data in the linked list.
  104.         LinkedList list = new LinkedList(new Node(5));
  105.         list.push(4);
  106.         list.push(3);
  107.         list.push(2);
  108.         list.push(1);
  109.  
  110.         // Setting up random references.
  111.         list.head.random = list.head.next.next;
  112.         list.head.next.random =
  113.             list.head.next.next.next;
  114.         list.head.next.next.random =
  115.             list.head.next.next.next.next;
  116.         list.head.next.next.next.random =
  117.             list.head.next.next.next.next.next;
  118.         list.head.next.next.next.next.random =
  119.             list.head.next;
  120.  
  121.         // Making a clone of the original linked list.
  122.         LinkedList clone = list.clone();
  123.  
  124.         // Print the original and cloned linked list.
  125.         System.out.println("Original linked list");
  126.         list.print();
  127.         System.out.println("\nCloned linked list");
  128.         clone.print();
  129.     }
  130. }
  131.  
  132. /* Name of the class has to be "Main" only if the class is public. */
  133. class Ideone
  134. {
  135. 	public static void main (String[] args) throws java.lang.Exception
  136. 	{
  137. 		// your code goes here
  138. 	}
  139. }
Success #stdin #stdout 0.08s 54692KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oH46pA
language:
Java (HotSpot 12)
created:
131 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!