Java: Merge Two Sorted Lists

Thought Process

To merge two sorted linked lists, we can either use a recursive approach or an iterative approach:

Approach 1: Recursive Approach - Handle edge cases where one of the lists is empty. Compare the current nodes of both lists. Recursively merge the remaining lists and link the smaller node to the result.

Approach 2: Iterative Approach - Start by handling edge cases where one of the lists is empty. Ensure list1 always points to the smaller starting node. Use a prev pointer to keep track of the last node in the merged list. Traverse both lists, appending the smaller node to the merged list and updating pointers.

Approach 1: Recursive Approach 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        
        if(list1==null)
            return list2;
            
        else if(list2==null)
            return list1;

        if(list1.val < list2.val){
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }
        else{
            list2.next = mergeTwoLists(list1,list2.next);
            return list2;
        }
    }
}

Approach 2: Iterative Approach 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        
        if(list1==null)
            return list2;

        if(list2==null)
            return list1;

            // Note: list1 always points to the linked list with smaller head
        // So, if list1.val > list2.val then we will swap them.
        if(list1.val > list2.val){ 
            ListNode tmp = list1;
            list1 = list2;
            list2 = tmp;
        }
        
        ListNode newHead = list1;
        
        while(list1!=null && list2!=null){
        
            ListNode prev = null;
            while(list1!=null && list1.val <= list2.val){
                prev  = list1;
                list1 = list1.next;
            }
            prev.next = list2;
            ListNode tmp = list1;
            list1 = list2;
            list2 = tmp;
        }
        return newHead;
    }
}

Code Complexity

Time Complexity: O(n + m)

Both approaches iterate through all nodes of the two lists, where 'n' and 'm' are the lengths of the two lists.

Space Complexity: O(n + m) or O(1)

The recursive approach uses stack space proportional to the sum of the lengths of the two lists, while the iterative approach uses constant space.

Code copied!