m2skills

merge sorted ll java

Jan 28th, 2018
28
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.90 KB | None | 0 0
  1. import java.util.Scanner;
  2.  
  3. /**
  4.  * Created by MOHIT on 24-01-2018.
  5.  */
  6.  
  7. class node{
  8.  
  9.     public int element;
  10.     public node link;
  11.  
  12.     //constructor that accepts only element
  13.     node(int element) {
  14.         this.element = element;
  15.         this.link = null;
  16.     }
  17.  
  18.     //constructor that accepts both link and element
  19.     node(int element, node link){
  20.         this.element = element;
  21.         this.link = link;
  22.     }
  23.  
  24.     //method to update the element
  25.     void updateData(int element){
  26.         this.element = element;
  27.     }
  28.  
  29.     //method to update or setup link
  30.     void updateLink(node link){
  31.         this.link = link;
  32.     }
  33.  
  34.     //method to get the element from the node
  35.     int getElement(){
  36.         return this.element;
  37.     }
  38.  
  39.     //method to get the next node
  40.     node getNextNode(){
  41.         return this.link;
  42.     }
  43. }
  44.  
  45. class LL {
  46.  
  47.     Scanner sc = new Scanner(System.in);
  48.     node head;
  49.  
  50.     void insertAtStart(int number){
  51.  
  52.         node newNode = new node(number);
  53.  
  54.         if(head == null){
  55.             head = newNode;
  56.         } else {
  57.             newNode.updateLink(head);
  58.         }
  59.         head = newNode;
  60.  
  61.         return;
  62.     }
  63.  
  64.     void insertAtEnd(int element){
  65.         if(head == null){
  66.             this.insertAtStart(element);
  67.             return;
  68.         }
  69.         node current = this.head;
  70.         while(current.getNextNode() != null){
  71.             current = current.getNextNode();
  72.         }
  73.  
  74.         node newNode = new node(element);
  75.         current.updateLink(newNode);
  76.         return;
  77.     }
  78.  
  79.     void display(){
  80.         node current = this.head;
  81.  
  82.         while(current!= null){
  83.             System.out.print(current.getElement());
  84.             if(current.getNextNode() != null){
  85.                 System.out.print("-->");
  86.             }
  87.             current = current.getNextNode();
  88.         }
  89.     }
  90.  
  91.  
  92.     // merge 2 sorted linked lists
  93.     void merge(node head2){
  94.         node head = null;
  95.         node current = null;
  96.         node curr1 = this.head;
  97.         node curr2 = head2;
  98.  
  99.         while(curr1 != null && curr2 != null){
  100.             if(curr1.getElement() > curr2.getElement()){
  101.                 if(head == null){
  102.                     head = curr2;
  103.                     current = head;
  104.                 }else{
  105.                     current.updateLink(curr2);
  106.                     current = current.getNextNode();
  107.                 }
  108.                 curr2 = curr2.getNextNode();
  109.             }else{
  110.                 if(head == null){
  111.                     head = curr1;
  112.                     current = head;
  113.                 }else{
  114.                     current.updateLink(curr1);
  115.                     current = current.getNextNode();
  116.                 }
  117.                 curr1 = curr1.getNextNode();
  118.             }
  119.         }
  120.  
  121.         if(curr1 != null){
  122.             current.updateLink(curr1);
  123.             current = current.getNextNode();
  124.         }
  125.  
  126.         if(curr2 != null){
  127.             current.updateLink(curr2);
  128.             current = current.getNextNode();
  129.         }
  130.  
  131.         this.head = head;
  132.     }
  133.  
  134. }
  135. public class LinkedList {
  136.     public static void main(String arg[]) {
  137.         System.out.println("Program to merge 2 sorted Linked Lists.");
  138.         LL l1 = new LL();
  139.         l1.insertAtEnd(1);
  140.         l1.insertAtEnd(3);
  141.         l1.insertAtEnd(5);
  142.         l1.insertAtEnd(7);
  143.         l1.insertAtEnd(9);
  144.         l1.insertAtEnd(11);
  145.         l1.insertAtEnd(13);
  146.         l1.insertAtEnd(15);
  147.         System.out.println("\nFirst linked list is : ");
  148.         l1.display();
  149.  
  150.         LL l2 = new LL();
  151.         l2.insertAtEnd(2);
  152.         l2.insertAtEnd(4);
  153.         l2.insertAtEnd(6);
  154.         l2.insertAtEnd(8);
  155.         l2.insertAtEnd(9);
  156.         System.out.println("\nSecond linked list is : ");
  157.         l2.display();
  158.  
  159.         System.out.println("\nAfter merging the Linked List is : ");
  160.         l1.merge(l2.head);
  161.         l1.display();
  162.     }
  163. }
Add Comment
Please, Sign In to add comment