Merge Two Sorted Lists

Problem

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.

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]

Constraints:

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

Solution

Approach 1: Iterative with Dummy Node

The key insight is to use a dummy node to simplify edge cases. We compare values from both lists and append the smaller node to our result list.

Algorithm:

Create a dummy node to serve as the start of the merged list
Use a pointer to track the current end of the merged list
Compare values from list1 and list2, append the smaller one
Handle remaining nodes from either list
Return dummy.next (the actual head)

Implementation

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        current = dummy

        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

        # Append remaining nodes
        current.next = list1 if list1 else list2

        return dummy.next

Approach 2: Recursive

The recursive approach chooses the smaller head, then recursively merges the rest.

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # Base cases
        if not list1:
            return list2
        if not list2:
            return list1

        # Choose smaller value as current node
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

Complexity Analysis

Iterative:

Time Complexity: O(n + m), where n and m are the lengths of the two lists. We visit each node once.
Space Complexity: O(1), we only use a constant amount of extra space.

Recursive:

Time Complexity: O(n + m), we visit each node once.
Space Complexity: O(n + m) due to recursion stack depth.

Key Insights

Dummy Node Pattern: Using a dummy node simplifies the code by eliminating special cases for the head of the list. We always have a valid node to append to.
In-Place Merging: We reuse the existing nodes from both lists rather than creating new nodes. We just rearrange pointers.
Remaining Nodes: After one list is exhausted, we can directly append the remainder of the other list since it’s already sorted.
Comparison Logic: We use <= instead of < to maintain stability (if values are equal, take from list1 first).
Recursive Insight: At each recursive step, we choose the smaller head and let recursion handle merging the rest. The base cases handle when one or both lists are empty.