21. Merge Two Sorted Lists

EasyLinked Lists and Pointer ManipulationMerge with a dummy tail pointerTwo-pointer merge

Merge Two Sorted Lists

Given the heads of two sorted singly linked lists, splice their nodes together into one sorted list and return its head. The result should be built by reusing the existing nodes.

Open official problem prompt ↗

In plain English

Interleave two sorted lists into one sorted list by relinking existing nodes, using no extra data structures.

Picture it like this

Merging two sorted stacks of numbered cards: each turn you compare the top card of each stack and place the smaller onto the output pile.

Example

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Why: Repeatedly taking the smaller current head yields 1,1,2,3,4,4 in sorted order.

Constraints

The number of nodes in both lists is in the range [0, 50]-100 <= Node.val <= 100Both list1 and list2 are sorted in non-decreasing order

Pattern lesson

See the pattern, then code

Two-pointer merge

↗

Linked Lists and Pointer Manipulation

Reversal, cycle detection, merging, reordering, or O(1)-space sequence edits.. At every moment the smallest unused value is one of the two current heads, so compare them and append the smaller, advancing only that list.

New words, made simpleKnow these before the algorithm

Tail pointer: A pointer to the last node of the list being built, so appends are O(1).
Stable merge: When values tie, taking from list1 first preserves relative order.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Collect and sort

Ignores the fact that inputs are already sorted; wasteful in time and space.

Dump all values into an array, sort, and rebuild a list.

Time O((n+m) log(n+m))Space O(n+m)

Best choiceTwo-pointer splice with dummy

Linear time, constant extra space, and reuses the given nodes.

Walk both lists at once, always appending the smaller head to a shared tail.

Time O(n+m)Space O(1)

The rule we keep true

Invariant

Everything already linked after dummy is sorted, and every value there is less than or equal to both current heads list1 and list2.

Why this is correct

Reasoning

Because both inputs are sorted, the global minimum among unused nodes is always one of the two heads; appending it and advancing keeps the invariant, and the leftover tail is already sorted so it can be attached wholesale.

The algorithm in three movesSay these aloud before coding

1Create a dummy node and a tail pointer starting at it

compare 1(l1) vs 1(l2) -> take l2 head

2While both lists are non-empty, attach the smaller head to tail and advance that list

compare 1(l1) vs 3(l2) -> take l1 head

3Advance tail

tail so far: 1 -> 1

4Attach whichever list still has remaining nodes

5Return dummy.next

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read1 vs 1

2 · AskWhich head is smaller?

3 · Update statetie -> take list1

4 · Resultmerged: 1; list1 -> 2,4

Key takeaway

The two heads are compared and the smaller is appended to the growing merged tail.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Dummy and tail
Dummy anchors the result so the first append needs no special case; tail marks where to append.
2
Lines 5-12Merge loop
Compare heads, attach the smaller with <= for stability, and advance that list plus tail.
3
Lines 13Attach leftovers
At most one list remains and it is already sorted, so link it in one move.
4
Lines 14Return
dummy.next is the real merged head.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

One or both lists empty
All values in one list smaller than the other
Equal values across lists (tie handling)

Common beginner mistakes

Using < instead of <= is still correct but reverses tie order; forgetting to advance tail causes a broken or infinite chain
Not attaching the remaining list after the loop
Returning dummy instead of dummy.next

Check your understanding

Why can the leftover list be attached without further comparisons?

Merge Two Sorted Lists

Merge Two Sorted Lists

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Linked Lists and Pointer Manipulation