21. Merge Two Sorted Lists

#linked-list

Problem

Merge Two Sorted Lists - LeetCodeLeetCode

Intuition

Time Complexity

Space Complexity

Solution

Iterative

/**
 * 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 l1, ListNode l2) {
    // n -> no.of nodes in l1
    // m -> no.of nodes in l2
    // Time complexity: O(n+m)
    // Space complexity:O(1), Auxillary space complexity
    
    if(l1 == null || l2 == null) { // If any of the list is null
        return l1 == null ? l2 : l1; // Return the other list
    }
    
    ListNode dummy = new ListNode(0); // Creating a dummy node
    ListNode head = dummy; // Assigning dummy node to head
    
    while(l1 != null && l2 != null) {
        if(l1.val <= l2.val) { // Condition two check sorted order
            // Asssign the lowest value node b/w l1 and l2 to dummy.next
            dummy.next = l1; 
            // Move forward with l1 node, as the current one is processed
            l1 = l1.next; 
        } else {
            // The above inference can be implied here too
            dummy.next = l2;
            l2 = l2.next;
        }
        // Move forward with dummy, so that the l1 and l2 nodes are appended
        dummy = dummy.next;
    }
    // Check if any list is not yet processed, then append them to dummy
    dummy.next = l1 != null ? l1 : l2;
    
    // In the beginning, we assign he head as dummy pointer
    // The first node of head is dummy(0), so we need to return the head.next
    return head.next;
}
}

Recursive

/**
 * 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 l1, ListNode l2) {
        if(l1 == null || l2 == null) {
            return l1==null ? l2 : l1;
        }
        
        if(l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}