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