How to Merge two sorted LinkedList Recursively in Java? Explained with Stack Trace

Merging two sorted Linked List using Recursion approach with Stack trace

First we will create two sorted Linked list and then merge them using recursion approach. Lets jump on code. 

public class MergeSortedLLRecursively {
    
    // Static nested inner class
    static class Node {
        int data;
        Node next;
        
        Node (int data) {
            this.data = data;
        }
        
        public void setData(int data) {
            this.data = data;
        }
        
        public void setNext(Node next) {
            this.next = next;
        }
    }
    
    static Node mergeList(Node n1, Node n2) {
        if (n1 == null) {
            return n2;
        }
        
        if (n2 == null) {
            return n1;
        }
        
        if (n1.data <= n2.data) {
            n1.next = mergeList(n1.next, n2);
            return n1;
        } else {
            n2.next = mergeList(n1, n2.next);
            return n2;
        }
    }
    
    static void printLinkedList(Node head) {
        Node current = head;   
        
        while(current != null) {    
            System.out.print(current.data + " ");    
            current = current.next;    
        }    
    }   
    
    public static void main(String[] args) {
        
        //Creating sorted list1 with setting next
        Node i1 = new Node(1);
        Node i2 = new Node(5);
        Node i3 = new Node(9);
        Node i4 = new Node(13);
        i1.setNext(i2);
        i2.setNext(i3);
        i3.setNext(i4);
        
        //Creating sorted list2 with setting next
        Node j1 = new Node(2);
        Node j2 = new Node(6);
        Node j3 = new Node(8);
        Node j4 = new Node(15);
        j1.setNext(j2);
        j2.setNext(j3);
        j3.setNext(j4);
        
        Node sortedList = mergeList(i1, j1);
        printLinkedList(sortedList);
    }
}

Output :

1 2 5 6 8 9 13 15 

Code explanation :

• When we call mergeList(), Stack trace will looks like as above pic. 
• In mergerList(), 
• first we have checked for n1 or n2 is null or not, based on that we will return. If anyone is null no need to merge anything.
  
• In next if condition, we will start comparing from first value of both list (1, 2). 
• In both if and else condition, we are calling mergeList() method recursively (as shown in above pic) and after recursion call over, it will link next Node based on sorting order.
  
• At last, return starting node from n1 or n2 based on lowest value.

  

Other articles you may like :

• How to Reverse Linked List in Java? | Iterative and Recursive approach 
• Inner class and its 4 types with example