Algorithm

Merge Two Sorted Lists

Two Pointer Pattern

Merge Two Sorted Lists

Merge two sorted linked lists into one. Splicing should be done by moving existing nodes, not creating new ones.

CONSTRAINTS
  • Nodes: 0 to 50 per list
  • -100 <= Node.val <= 100
  • Input lists are already sorted.
EXAMPLE 1
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Reading the two sorted lists together and always taking the smaller front value produces one sorted sequence.
EXAMPLE 2
Input: list1 = [], list2 = [0]
Output: [0]
One list is empty, so the result is just the other list unchanged.
EXAMPLE 3
Input: list1 = [], list2 = []
Output: []
Both lists are empty, so there is nothing to merge.
Should I create new nodes or reuse the existing ones?
Reuse the existing nodes by relinking their .next pointers. No new nodes are needed.
What if one or both lists are empty?
If one is empty, return the other. If both are empty, return null.
How are ties (equal values) handled?
Take either one; taking from the first list on a tie keeps the merge stable, which is the conventional choice.

Merging two sorted lists is essentially about consolidating disparate, ordered data streams into a single, cohesive timeline. Since each list is already sorted, the globally next-smallest element must reside at the head of one of the two lists, allowing us to make local decisions that guarantee a globally sorted result.

The Brute Force Approach (O((N+M) log (N+M)))

The naive way to solve this is to collect all nodes from both lists into a new array, sort that array, and then create a completely new linked list from the sorted values. While this works, it requires O(N+M) extra space and ignores the fact that the inputs are already sorted. This is inefficient when we can simply re-route existing pointers.

python
# Brute force: collect, sort, and rebuild
def brute_force(l1, l2):
    nodes = []
    while l1: nodes.append(l1.val); l1 = l1.next
    while l2: nodes.append(l2.val); l2 = l2.next
    nodes.sort()
    
    dummy = Node(0)
    curr = dummy
    for val in nodes:
        curr.next = Node(val)
        curr = curr.next
    return dummy.next
The Two-Pointer Insight

Because the lists are pre-sorted, we don't need to gather or re-sort anything. At any point, we simply look at the heads of both lists and pick the smaller one to be the next node in our new list. By maintaining a pointer on the head of each list and moving them forward as we pick nodes, we can construct the result list in a single pass.

Optimal Strategy: Pointer Re-routing

We use a Dummy Node to act as a stable starting anchor for our result list, which simplifies our logic and avoids edge cases when initializing the head. We keep a tail pointer to append nodes to our new list.
- Compare the current nodes of l1 and l2.
- Append the smaller node to tail and move that list's pointer forward.
- Once one list is exhausted, we simply "leak" the remainder of the other list by pointing tail.next to the remaining nodes, as they are already in the correct sorted order.

python
# Optimal: iterative pointer re-routing
def merge_two_lists(l1, l2):
    dummy = Node(0)
    tail = dummy
    while l1 and l2:
        if l1.val < l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    # Attach remaining part
    tail.next = l1 or l2
    return dummy.next
Worked Example:[1, 2, 4] + [1, 3, 4]
0
dummy/tail
→
NULL
We initialize our merged list with a dummy node 0.
0
→
1
tail
→
NULL
We compare the heads of both lists: 1 (l1) and 1 (l2). We choose l1's node and append it to our list, shifting l1.
0
→
1
→
1
tail
→
NULL
We compare 2 (l1) and 1 (l2). We append l2's node and shift l2 forward.
0
→
1
→
1
→
2
tail
→
NULL
We compare 2 (l1) and 3 (l2). We append l1's node and shift l1 forward.
0
→
1
→
1
→
2
→
3
→
4
→
4
→
NULL
When one list is exhausted, we stitch the remaining nodes directly to the tail. We return dummy.next, yielding [1, 1, 2, 3, 4, 4].
Interactive Strategy Visualization
MERGE HARMONIZER

Iterative Two-Pointer Sync

List 1 (L1)
1
2
4
List 2 (L2)
1
3
4
Unified Sorted Result

Current Focus

Phase 1: Dual Sentinel Entry

We use a Dummy Node as our anchor. Pointers L1 and L2 stand at the gates of our two sorted streams.

Efficiency Note

We reuse existing node pointers. No new nodes are created (except the dummy), making this an **O(1) extra space** operation.

Strategy: Tail Appending

By comparing nodes one by one and appending the smaller to the new tail, we build the final list in a single pass of O(N + M).

O((N+M) log(N+M)) Collect & Sort
→
O(N + M) Time · O(1) Space Two-Pointer Merge