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 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

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