Merge Two Sorted Lists — DSA Visualizer

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

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

empty

Variables

p1.val

—

p2.val

—

Comparison

—

Result Length

Step Logic

Press ▶ Play or Next Step to begin the animation.

Ready

0 / 0

Select an example above and press Play.

Algorithm

Create dummy = new ListNode(0); set curr = dummy.

While p1 != null && p2 != null: enter comparison loop.

If p1.val ≤ p2.val: append p1 to result, advance p1.

Else: append p2 to result, advance p2.

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.