Merge Two Sorted Lists

easyLinked List30 stepsJava · Python · C++

Merge two sorted lists into one sorted list by splicing nodes. A dummy head avoids special cases: repeatedly attach the smaller front node to the tail, then attach whatever remains.

▶ Watch the animated trace

Traced input: list1 = [1, 2, 4], list2 = [1, 3, 4] → [1, 1, 2, 3, 4, 4]. Original problem: neetcode.io/problems/merge-two-sorted-linked-lists

Complexity

BestO(n + m)

AverageO(n + m)

WorstO(n + m)

SpaceO(1)

Nodes are relinked, not copied.

Key idea

A dummy node means the result's head is always dummy.next.
Compare the two fronts, attach the smaller one, advance that list.
When one list runs out, attach the other in one step; it's already sorted.

Common mistakes

Losing the head by not using a dummy node.
Forgetting to attach the leftover list.
Using < vs <= doesn't matter for correctness, but <= keeps it stable.

Solution

Java

ListNode mergeTwoLists(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0), tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) {
            tail.next = a;
            a = a.next;
        } else {
            tail.next = b;
            b = b.next;
        }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;
    return dummy.next;
}

Python

def mergeTwoLists(a: Optional[ListNode], b: Optional[ListNode]) -> Optional[ListNode]:
    dummy = tail = ListNode(0)
    while a and b:
        if a.val <= b.val:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a if a else b
    return dummy.next

C++

ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) {
            tail->next = a;
            a = a->next;
        } else {
            tail->next = b;
            b = b->next;
        }
        tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Both empty dummy.next stays null.	`list1 = [], list2 = []`	`[]`
One empty The other list is attached whole.	`list1 = [], list2 = [0]`	`[0]`
No overlap list1 runs out first; list2 is attached in one step.	`list1 = [1, 2], list2 = [5, 6]`	`[1, 2, 5, 6]`
Negatives and duplicates Ties take from list1 first.	`list1 = [-3, 0, 0], list2 = [-3, 1]`	`[-3, -3, 0, 0, 1]`