Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Scanner;
- /**
- * Created by MOHIT on 24-01-2018.
- */
- class node{
- public int element;
- public node link;
- //constructor that accepts only element
- node(int element) {
- this.element = element;
- this.link = null;
- }
- //constructor that accepts both link and element
- node(int element, node link){
- this.element = element;
- this.link = link;
- }
- //method to update the element
- void updateData(int element){
- this.element = element;
- }
- //method to update or setup link
- void updateLink(node link){
- this.link = link;
- }
- //method to get the element from the node
- int getElement(){
- return this.element;
- }
- //method to get the next node
- node getNextNode(){
- return this.link;
- }
- }
- class LL {
- Scanner sc = new Scanner(System.in);
- node head;
- void insertAtStart(int number){
- node newNode = new node(number);
- if(head == null){
- head = newNode;
- } else {
- newNode.updateLink(head);
- }
- head = newNode;
- return;
- }
- void insertAtEnd(int element){
- if(head == null){
- this.insertAtStart(element);
- return;
- }
- node current = this.head;
- while(current.getNextNode() != null){
- current = current.getNextNode();
- }
- node newNode = new node(element);
- current.updateLink(newNode);
- return;
- }
- void display(){
- node current = this.head;
- while(current!= null){
- System.out.print(current.getElement());
- if(current.getNextNode() != null){
- System.out.print("-->");
- }
- current = current.getNextNode();
- }
- }
- // merge 2 sorted linked lists
- void merge(node head2){
- node head = null;
- node current = null;
- node curr1 = this.head;
- node curr2 = head2;
- while(curr1 != null && curr2 != null){
- if(curr1.getElement() > curr2.getElement()){
- if(head == null){
- head = curr2;
- current = head;
- }else{
- current.updateLink(curr2);
- current = current.getNextNode();
- }
- curr2 = curr2.getNextNode();
- }else{
- if(head == null){
- head = curr1;
- current = head;
- }else{
- current.updateLink(curr1);
- current = current.getNextNode();
- }
- curr1 = curr1.getNextNode();
- }
- }
- if(curr1 != null){
- current.updateLink(curr1);
- current = current.getNextNode();
- }
- if(curr2 != null){
- current.updateLink(curr2);
- current = current.getNextNode();
- }
- this.head = head;
- }
- }
- public class LinkedList {
- public static void main(String arg[]) {
- System.out.println("Program to merge 2 sorted Linked Lists.");
- LL l1 = new LL();
- l1.insertAtEnd(1);
- l1.insertAtEnd(3);
- l1.insertAtEnd(5);
- l1.insertAtEnd(7);
- l1.insertAtEnd(9);
- l1.insertAtEnd(11);
- l1.insertAtEnd(13);
- l1.insertAtEnd(15);
- System.out.println("\nFirst linked list is : ");
- l1.display();
- LL l2 = new LL();
- l2.insertAtEnd(2);
- l2.insertAtEnd(4);
- l2.insertAtEnd(6);
- l2.insertAtEnd(8);
- l2.insertAtEnd(9);
- System.out.println("\nSecond linked list is : ");
- l2.display();
- System.out.println("\nAfter merging the Linked List is : ");
- l1.merge(l2.head);
- l1.display();
- }
- }
Add Comment
Please, Sign In to add comment