Merge Two Sorted Lists

Problem Statement

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

Constraints:
1. The number of nodes in both lists is in the range [0, 50]
2. -100 <= Node.val <= 100
3. Both list1 and list2 are sorted in non-decreasing order

Examples:

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Solution

Approach 1: Recursion

This approach is very intuitive and easy to implement. We can recursively define the result of a merge operation on two lists as the following:

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def mergeTwoLists_Recursive(self, list1, list2):
        """
        Approach 1: Recursion
        - Time Complexity: `O(n + m)`
        - Space Complexity: `O(n + m)`
        """
        if not list1:
            return list2
        if not list2:
            return list1
        if list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

    def printList(self, list1):
        res_list = []
        while list1:
            ## convert as a list
            res_list = res_list + [list1.val]
            list1 = list1.next
        print(res_list)

Approach 2: Iteration

Think about how we would merge two lists by hand. We would compare the first elements of each list and add the smaller one to the merged list. After adding an element, we would move the pointer in the respective list one step forward. By repeating this process, we would eventually reach the end of at least one of the lists, and we would know that we can add all the elements from the other list to the merged list.

class Solution(object):
    def mergeTwoLists(self,list1,list2):
        """
        Approach 1: Iteration
        - Time Complexity: `O(n + m)`
        - Space Complexity: `O(1)`
        """
        dummy = ListNode()  # Dummy node to simplify merging
        current = dummy  # Pointer to the current node in the merged list

        while list1 and list2:
            if list1.val < list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next

        # If there are remaining elements in either list, append them
        if list1:
            current.next = list1
        if list2:
            current.next = list2

        return dummy.next  # The merged list starts from the next node of the dummy