Merge two sorted singly linked lists in java (example / recursive)

• Given the two sorted linked lists in java.
• We would to merge two sorted linked lists into single linked list, such that resultant linked list is sorted.
• Let us take an example to understand our problem statement.

We have shown two sorted linked lists in Fig 1 and Fig 2. We would merge two linked list.

• Merged single linked list will contain nodes from both linked lists.
• Merged single linked list shall be sorted one.

Algorithm or recursive method to merge two sorted linked lists in java

• Create merge method, taking head1 and head2 as method parameter
  • merge(Node head1, Node head2)
  • Create variable mergedList, which will point to head of merge linked list
• Let us look into recursive merge method
• If we reached end of first linked list
  • return second linked list
  • so that, mergedList start point to second linked list
• If we reached end of second linked list
  • return first linked list
  • so that, mergedList start pointing first linked list
• If we are here, then compare
  • Check head1.data < head2.data
    • mergedList point to head1
    • now lets move ahead in linked list
      • head1.next and head2
  • We are here, head1.data >= head2.data
    • mergeList points to head2
    • lets move ahead in linked list
      • head1 and head2.next
• return mergedList [resultant linked list]

Merged Linked list: We have shown the merged linked list in Fig 4, The merged linked list satisfy the criteria which we have defined earlier.

Program – Merge two sorted singly linked lists in java (recursive algorithm)

1.) MergeLinkedLists Class:

The MergeLinkedLists class has following methods

• insert function will insert elements to single linked list
• print function will print the single linked list
• merge function will merge the two linked lists

package org.learn.Question;

import org.learn.List.Node;

public class MergeLinkedLists {
 
 public static Node merge(Node head1, Node head2) {
  Node mergedList = null;
  if(head1 == null) {
   return head2;
  }
  if(head2 == null) {
   return head1;
  }
  if(head1.data < head2.data) {
   //point to smaller element
   mergedList = head1;   
   mergedList.next = merge(head1.next, head2);
  } else { //head1 is large, so pass h
   //point to smaller element
   mergedList = head2;
   //head2 is already consider
   //now process next node of head2
   mergedList.next = merge(head1, head2.next);
  }
  return mergedList;
 }
 
 public static void insert(Node head, int data) {
  while(head.next != null) 
   head = head.next;
  head.next = new Node(data);
 }
 
 public static void print(Node head) {
  while(head != null) {
   System.out.printf("%d ",head.data);
   head = head.next;
  }
  System.out.println("");  
 }
}

2.) App Class:

We are performing the following operation in App class

• We are creating two linked lists in main method.
• MergeLinkedLists.merge will merge two single linked lists
• We are printing the linked list after merging the two linked list
  • MergeLinkedLists.print will print the single linked list

package org.learn.Client;
import org.learn.List.Node;
import org.learn.Question.MergeLinkedLists;

public class App 
{
    public static void main( String[] args )
    {
  int[] data1 = {1,3,5,9};
  Node head1 = new Node(data1[0]);
  for(int count = 1; count < data1.length; count++)
   MergeLinkedLists.insert(head1,data1[count]);
  
  System.out.printf("Linked list 1 is : ");
  MergeLinkedLists.print(head1);
  
  int[] data2 = {2,4,5,6,10};
  Node head2 = new Node(data2[0]);
  for(int count = 1; count < data2.length; count++)
   MergeLinkedLists.insert(head2,data2[count]);
  
  System.out.printf("Linked list 2 is : ");
  MergeLinkedLists.print(head2);
  
  Node mergedList = MergeLinkedLists.merge(head1, head2);
  System.out.printf("Merged Linked list is : ");
  MergeLinkedLists.print(mergedList);
    }
}

3.) Node Class:

• Node class representing the node(s) of a single linked list

package org.learn.List;
public class Node { 
 public int data;
 public Node next;
 public Node(int num) {
    this.data = num;
    this.next = null;
 }
}

Output – Merge two sorted singly linked lists in java (recursive algorithm)

Linked list 1 is : 1 3 5 9
Linked list 2 is : 2 4 5 6 10
Merged Linked list is : 1 2 3 4 5 5 6 9 10

Download code – Merge two sorted linked lists (recursive method) in java