pastebin

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