Merge Two Sorted Lists

LeetCode #21 [Easy]

Problem Statement

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted linked list and return its head.

Example: Input: 1 → 2 → 4, 1 → 3 → 4 → Output: 1 → 1 → 2 → 3 → 4 → 4

Approach 1: Iterative Merge

Explanation: Use a dummy node and append smaller node at each step.

Time Complexity: O(m+n)

Space Complexity: O(1)

dummy = new Node(-1)
tail = dummy
while list1 != NULL and list2 != NULL:
    if list1.val < list2.val:
        tail.next = list1
        list1 = list1.next
    else:
        tail.next = list2
        list2 = list2.next
    tail = tail.next
tail.next = list1 if list1 != NULL else list2
return dummy.next

💡 Think: Use a dummy tail and always attach the smaller head next.

Approach 2: Recursive Merge

Explanation: Compare heads recursively and build merged list.

Time Complexity: O(m+n)

Space Complexity: O(m+n) (recursion stack)

if list1 == NULL:
    return list2
if list2 == NULL:
    return list1
if list1.val < list2.val:
    list1.next = merge(list1.next, list2)
    return list1
else:
    list2.next = merge(list1, list2.next)
    return list2

💡 Think: Pick the smaller head, recurse on the remainder, then link back.

Solve on LeetCode