Merge two sorted linked lists

Merge two sorted linked lists

In this article, we are going to learn how to merge two linked lists. Here we have given two linked lists that are sorted in increasing order, and we need to merge them into one list, which will also be in increasing order.

Example:

Suppose, the first linked list is 3 -> 5 -> 8 and the second linked lists is 2 -> 4 -> 6. Now, we will merge them into one list and the pointer to the head node of the merged list will return 2 -> 3 -> 4 -> 5 -> 6 -> 8.

Using two pointers method

This method will traverse both the linked lists till the end, compare the nodes of both the linked lists, and check which of the node has a larger value. The larger node will be added to the resultant or merged linked list.

Algorithm:

1) First, initialize the resultant linked list as empty: head = NULL.

2) We will take two pointers head1 and head2, as the starting pointer of the first and second linked list.

3) Then, we will traverse both the linked list till the end:

    While (head1 != NULL and head2 != NULL)

    a) After this, we will check which node contains the greater value.

    b) Then, we will add or insert a larger value node in the resultant linked list.

4) If the head2 or second linked list becomes NULL before the first linked list, then we will add all nodes of the first linked list in the resultant linked list.

5) If the head1 or first linked list becomes NULL before the second linked list, then we will add all nodes of the second linked list in the resultant linked list.

Source code to merge two sorted linked lists in Java:

 import java.util.*;
 class Node
 {
     int data;
     Node next;
     Node(int d) {
         data  =  d;
         next  =  null;
     }
 }
 class MergeLists
 {
   /* Function to print linked list */
    public static void printList(Node head)
     {
         System.out.println("The merged linked list is:");
         while (head!= null)
         {
            System.out.print(head.data+" ");
            head  =  head.next;
         } 
         System.out.println();
     }
      /* Driver program to test above functions */
     public static void main(String args[])
     {
          Scanner sc  =  new Scanner(System.in);
          System.out.println("Enter the total no of elements for first linked list:");          
              int n1 = sc.nextInt();
              System.out.println("Enter the total no of elements for second linked list:");
              int n2 = sc.nextInt();
              System.out.println("Enter the elements for first linked list:");
              Node head1 = new Node(sc.nextInt());
             Node tail1  =  head1;
             for(int i = 0; i<n1-1; i++)
             {
                 tail1.next  =  new Node(sc.nextInt());
                 tail1  =  tail1.next;
             }
              System.out.println("Enter the elements for second linked list:");
              Node head2 = new Node(sc.nextInt());
             Node tail2 = head2;
             for(int i = 0; i < n2-1; i++)
             {
                 tail2.next = new Node(sc.nextInt());
                 tail2 = tail2.next;
             }
                                     LinkedList obj  =  new LinkedList();
                                     Node head  =  obj.sortedMerge(head1,head2);
                                     printList(head);                    
     }
 }
 // } Driver Code Ends
 class LinkedList
 {
     //Function to merge two sorted linked lists.
     Node sortedMerge(Node head1, Node head2) {
      Node head = null;
     Node t = null;
     while(head1!=null && head2!=null)
     {
         if(head1.data<=head2.data)
         {
             if(head==null)
             {
                 head = new Node(head1.data);
                 t = head;
             }
             else
             {
                 t.next = new Node(head1.data);
                 t = t.next;
             }
             head1 = head1.next;
         }
         else
         {
             if(head == null)
             {
                 head = new Node(head2.data);
                 t = head;
             }
             else
             {
                 t.next = new Node(head2.data);
                 t = t.next;
             }
             head2 = head2.next;
         }
     }
     while(head1!= null)
     {
         t.next = new Node(head1.data);
         t = t.next;
         head1 = head1.next;
     }
     while(head2 != null)
     {
         t.next = new Node(head2.data);
         t = t.next;
         head2 = head2.next;
     }
     return head;
    }
 } 

Output: -