Why use a dummy node to merge two sorted lists?

Without it, the first node of the result needs special handling, because there is no previous node to link it after. The dummy gives tail somewhere to start, and dummy.next is the merged head at the end.

What is the time and space complexity of merging two sorted lists?

O(n + m) time in the worst case, since each node is linked once, and O(1) extra space: the iterative version only rewires next pointers. The recursive version also takes O(n + m) time but uses O(n + m) stack space.

What happens when one list runs out first?

The rest of the other list is already sorted and every value in it is at least as large as everything merged so far, so it is linked after tail in a single step.

Merge Two Sorted Lists

Merge two sorted linked lists into one sorted list by splicing nodes after a dummy head.

EasySolve on LeetCode

Problem Understanding

Merge Two Sorted Lists: given the heads of two sorted linked lists list1 and list2, splice their nodes together into one sorted list and return its head. The nodes are reused, not copied.

Example: 1 -> 2 -> 4 and 1 -> 3 -> 4 merge into 1 -> 1 -> 2 -> 3 -> 4 -> 4.

Attempt 1: Collect and Sort

Copy every value from both lists into an array, sort it, and build a new list. It works, but it costs O((n + m) log(n + m)) time and O(n + m) extra space, and it ignores the fact that both inputs are already sorted. A merge only ever needs to look at the two current heads.

The Intuition: Always Take the Smaller Head

The smallest remaining value is always one of the two heads, so the merged list can be built front to back:

Point tail at a dummy node, so the first real node is linked like every other.
While both lists have nodes, link the smaller head after tail (list1's on a tie, which keeps equal values in their original order) and advance that list and tail.
When one list is empty, link the remainder of the other in one step — it is already sorted.
Return dummy.next.

Interactive Walkthrough

D = DUMMY HEAD · L1 / L2 = THE LIST A NODE CAME FROM

DUMMY HEAD

merged

tail

→

NULL

list1

→

list2

→

Merged

list1 left

list2 left

tail starts at a dummy node, so the first real node needs no special case

Compare the heads: list1 has 1, list2 has 1

list1

list2

Legend & Complexity

list1’s head being compared, and the node just linked

list2’s head being compared

Already in the merged list

Already taken from its list

Time

O(n + m)

Space

O(1)

The merged list grows from the dummy node D on the top row; under it, list1 and list2 grey out as their nodes are taken. Each comparison lights both heads, and each merged node is tagged with the list it came from.

Dry Run Table

Input: list1 = 1 -> 2 -> 4, list2 = 1 -> 3 -> 4

Compare	Take	Merged so far
1 vs 1	list1's 1 (tie)	`1`
2 vs 1	list2's 1	`1 → 1`
2 vs 3	list1's 2	`1 → 1 → 2`
4 vs 3	list2's 3	`1 → 1 → 2 → 3`
4 vs 4	list1's 4 (tie)	`1 → 1 → 2 → 3 → 4`
list1 empty	attach list2's rest `4`	`1 → 1 → 2 → 3 → 4 → 4`

Return dummy.next.

The Solution Template

Iterative merge with a dummy head.

Merge Two Sorted Lists Code

1var mergeTwoLists = function(list1, list2) {
2    const dummy = new ListNode();
3    let tail = dummy;
4    while (list1 && list2) {
5        if (list1.val <= list2.val) {
6            tail.next = list1;
7            list1 = list1.next;
8        } else {
9            tail.next = list2;
10            list2 = list2.next;
11        }
12        tail = tail.next;
13    }
14    tail.next = list1 ?? list2;
15    return dummy.next;
16};

Edge Cases & Common Mistakes

Both lists empty: the loop never runs, tail.next becomes NULL, and dummy.next is NULL.
One list empty: the other is returned whole — attached after the dummy in one step.
Equal values: taking list1's node on a tie (<=) keeps equal values in their original order.
Forgetting the leftover: stopping when one list ends drops the rest of the other.
Returning dummy instead of dummy.next: the result would start with the placeholder node.

Summary

A dummy head and a tail pointer turn merging into one rule: take the smaller head. The same merge step is the core of merge sort, and of Merge K Sorted Lists, where a heap picks the smallest of k heads.

Reverse Linked List

Linked List Cycle