0021. Merge Two Sorted Lists

Easy | Linked List + Recursion | 16ms (98.84%), 13.4 MB (87.61%)

❓ Problem Statement

Source: LeetCode - Merge Two Sorted Lists GitHub: Solution / Performance

Merge two sorted linked lists and return them as a sorted list. The list should be made by "splicing" together (with) the nodes of the first two lists.

✍🏻 Constraints & Example

Constraints:

• The number of nodes in both lists is in the range [0, 50].

• -100 <= Node.val <= 100

• Both l1 and l2 are sorted in non-decreasing order.

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Input: l1 = [], l2 = []
Output: []

Input: l1 = [], l2 = [0]
Output: [0]

💡 Ideas

According to the problem statement, we cannot create a new linked list to store sorted nodes.

Therefore, top-down recursion could help us sort by in-place modification on either l1 or l2 as a starting node.

🤖 Python3

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        #  (base case)
        if not l2 and l1: return l1
        if not l1 and l2: return l2
        if not l1 and not l2: return None
        
        # ==================================================
        #  Linked List + Recursion                         =
        # ==================================================
        # n is the length of l1, and m is the length of l2
        # time  : O(n+m)
        # space : O(n+m)
            
        if l1.val > l2.val: l1, l2 = l2, l1
        l1.next = self.mergeTwoLists(l1.next, l2)
        
        return l1

🤖 Java

class Solution {
    /**
     * @time  : O(n+m)
     * @space : O(n+m)
     */
  
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        /* base case */
        if(l1 != null && l2 == null) return l1;
        if(l1 == null && l2 != null) return l2;
        if(l1 == null && l2 == null) return null;

        if(l2.val < l1.val) {
            ListNode tmp = l1;
            l1 = l2;
            l2 = tmp;
        }
        l1.next = mergeTwoLists(l1.next, l2);
        
        return l1;
    }
}