LeetCode 021 - Merge Two Sorted Lists

2026-07-08

easy　linked list　recursion

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted linked list and return the head. The merged list must be made up of nodes from list1 and list2.

Example 1:

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

Output: [1,1,2,3,4,5]

Example 2:

Input: list1 = [], list2 = [1,2]

Output: [1,2]

Example 3:

Input: list1 = [], list2 = []

Output: []

Constraints:

• 0 <= length of each list <= 100
• -100 <= Node.val <= 100
• Both lists are sorted in non-decreasing order.

Solution 1:

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # Approach: Iterative with Dummy Head
        # 1. Create a dummy node as the starting anchor — its next will be the merged head.
        # 2. Walk both lists simultaneously with a cur pointer:
        #    - Attach the node with the smaller value to cur.next.
        #    - Advance that list's pointer and move cur forward.
        # 3. When one list is exhausted, attach the remaining tail of the other directly.
        #    (The tail is already sorted, so no further comparison is needed.)
        # 4. Return dummy.next as the head of the merged list.
        # Time Complexity: O(N + M) — each node is visited once.
        # Space Complexity: O(1) — nodes are reused in place; only the dummy node is new.
        dummy = ListNode()
        cur = dummy
        list1_cur = list1
        list2_cur = list2

        while list1_cur and list2_cur:
            if list1_cur.val < list2_cur.val:
                cur.next = list1_cur
                list1_cur = list1_cur.next
            else:
                cur.next = list2_cur
                list2_cur = list2_cur.next
            cur = cur.next

        if list1_cur:
            cur.next = list1_cur
        elif list2_cur:
            cur.next = list2_cur

        return dummy.next

Solution 2:

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # Approach: Recursive
        # Base cases: if either list is empty, the other list is the answer.
        # Recursive step:
        # - Pick the node with the smaller value as the current head.
        # - Set its next to the result of merging its remaining tail with the other list.
        # - Return that node as the head of this sub-merge.
        # The recursion unwinds naturally once one side is exhausted.
        # Time Complexity: O(N + M) — one call per node.
        # Space Complexity: O(N + M) — recursion stack depth equals total node count.
        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(list2.next, list1)
            return list2

Conclusion

Today we merged two sorted linked lists two ways.

The iterative solution uses a dummy head as a stable anchor — it gives us a fixed node to build the merged list off, so we never need to special-case the head assignment. At each step we just pick the smaller of the two current nodes, attach it, and advance. When one list runs out, we splice the remaining tail directly since it's already sorted.

The recursive solution is more concise. At each call, whichever node has the smaller value becomes the current head, and its next is recursively set to the merge of the rest. The base cases handle empty inputs, and the recursion unwinds cleanly once either side is exhausted.

Both run in O(N + M) time. The iterative version uses O(1) extra space (just the dummy node); the recursive version uses O(N + M) stack space due to the call depth. For long lists, the iterative approach is safer to avoid stack overflow.