Merge Two Sorted Lists

Problem Description

Given the heads of two sorted linked lists list1 and list2, merge them into one sorted linked list by splicing together their nodes. Return the head of the merged list.

Examples

Constraints

• The number of nodes in both lists is in the range [0, 50].
• -100 ≤ Node.val ≤ 100
• Both lists are sorted in non-decreasing order.

A Dummy Head Eliminates All the Edge Cases

Without a dummy head, the first node of the merged list is a special case: you don’t yet have a curr.next to write to. You’d need either an if/else to initialize the merged head or a separate pre-loop step. A dummy head node sidesteps this entirely: curr always has a valid next slot to write into, even for the very first node. The real merged list starts at dummy.next.

Solution 1: Iterative with Dummy Head

Compare the heads of both lists. Append the smaller node to curr, advance that list’s pointer, advance curr. After one list is exhausted, attach the remaining tail of the other.

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0); // sentinel; merged list starts at dummy.next
        ListNode curr = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                curr.next = list1;
                list1 = list1.next;
            } else {
                curr.next = list2;
                list2 = list2.next;
            }
            curr = curr.next;
        }

        // at most one list still has nodes; attach the remainder directly
        curr.next = (list1 != null) ? list1 : list2;
        return dummy.next;
    }
}

class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        dummy = ListNode(0)  # sentinel; merged list starts at dummy.next
        curr = dummy

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

        # at most one list still has nodes; attach the remainder directly
        curr.next = list1 if list1 else list2
        return dummy.next

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(0);  // sentinel; merged list starts at dummy.next
        ListNode* curr = &dummy;

        while (list1 && list2) {
            if (list1->val <= list2->val) {
                curr->next = list1;
                list1 = list1->next;
            } else {
                curr->next = list2;
                list2 = list2->next;
            }
            curr = curr->next;
        }

        // at most one list still has nodes; attach the remainder directly
        curr->next = list1 ? list1 : list2;
        return dummy.next;
    }
};

Complexity Analysis:

• Time Complexity: O(m + n). Each node from both lists is visited exactly once.
• Space Complexity: O(1). We splice existing nodes; the only allocation is the dummy head.

Where it breaks: nothing breaks in the standard case. The subtle edge case is both lists empty: the while loop never runs, curr.next gets assigned null, and dummy.next is null. That’s the correct return value.

Solution 2: Recursive

At each step, pick the smaller head. Recursively merge the remainder.

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        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

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (!list1) return list2;
        if (!list2) return list1;
        if (list1->val <= list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

Complexity Analysis:

• Time Complexity: O(m + n). One recursive call per node.
• Space Complexity: O(m + n). Call stack depth equals total nodes.

Where it breaks: with lists of length 50 each, the recursion depth is at most 100. Stack overflow is not a concern at these sizes, but the pattern generalizes poorly to very large inputs.

Common Mistakes

• Advancing curr before setting curr.next. If you do curr = curr.next first and then curr.next = list1, you’ve moved curr to null and the write fails.
• Forgetting to attach the remainder after the while loop. Both lists are rarely exhausted simultaneously. One always runs out first. Not attaching the other’s tail loses all remaining nodes.
• Using curr.next.next to skip nodes. You’re merging, not skipping. Only curr.next assignment is needed; curr = curr.next advances the build pointer.

Frequently Asked Questions

Why attach the remainder with curr.next = list1 or list2 instead of looping? The remaining list is already sorted and already linked. You don’t need to re-append each node one by one. A single pointer assignment attaches the entire remaining tail.

What if the two lists have different lengths? The while loop exits when the shorter list runs out. The entire tail of the longer list gets attached in one assignment. No special handling needed.

How does this extend to merging k sorted lists? Merge repeatedly in pairs (divide and conquer). That’s “Merge k Sorted Lists” with O(N log k) time, where N is total nodes.

← All Problems