DSA AnimatorDSA animations
Merge Two Sorted Lists LC #21 Easy Linked List · Two Pointers
Problem

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list by splicing together the nodes of the two lists. Return the head of the merged linked list.

Example 1
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2
Input: list1 = [1,3,5], list2 = [2,4,6]
Output: [1,2,3,4,5,6]
Example 3
Input: list1 = [], list2 = [0]
Output: [0]
Constraints: 0 ≤ list length ≤ 50  |  −100 ≤ Node.val ≤ 100  |  Both lists sorted in non-decreasing order
Try Examples
Merge Visualization
list1 p1 blue pointer · active node highlighted blue
list2 p2 purple pointer · active node highlighted purple
merged curr green nodes appended one by one
Variables
p1.val
—
p2.val
—
Comparison
—
Result Length
0
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Create dummy = new ListNode(0); set curr = dummy.
2
While p1 != null && p2 != null: enter comparison loop.
3
If p1.val ≤ p2.val: append p1 to result, advance p1.
4
Else: append p2 to result, advance p2.
5
Attach remaining non-null list as tail. Return dummy.next.
Time
O(m+n)
Space
O(1)
Why It Works

Both input lists are already sorted. By always choosing the smaller front element, sorted order is maintained in the result. The dummy head eliminates special-casing the first insertion. When one list runs out, the remaining nodes of the other are already sorted — they can be appended directly as the tail without further comparisons.

How to solve Merge Two Sorted Lists

LeetCode 21 · Easy · Linked List · Pattern: Two Pointers Merge

Why the obvious approach is slow

Collecting all values, sorting them and building a new list costs O(n log n). Both lists are already sorted, so just merge.

The key idea

Start with a dummy node and a tail pointer. Compare the two heads, attach the smaller one to the tail, and advance that list. When one list runs out, attach the rest of the other.

Remember

A dummy head makes building a list easy. Always take the smaller head.

Run the animation above on your own input, or watch the 1:11 video explanation of Merge Two Sorted Lists with a dry run and Java code.

More Linked List problems