Linked List — Merge Two Sorted Lists

What does it solve?

Combine two already-sorted lists into a single sorted list, reusing the existing nodes (no copies). It's the merge half of merge sort, and the pattern behind merging k lists.

Key insight: keep a pointer into each list, a and b. Compare their heads, splice the smaller one onto the result tail, and advance that pointer. Repeat until one list empties, then attach the rest of the other (already sorted). A dummy head removes the "is the result empty yet?" special case: you always append to tail.next and return dummy.next at the end.

The core idea

// dummy + tail, pick smaller head
while a && b:
  if a.val <= b.val: tail.next=a; a=a.next
  else: tail.next=b; b=b.next
  tail = tail.next
tail.next = a ? a : b // attach remainder
return dummy.next

Complexity

Time complexity

O(N+M)

Each node from both lists is looked at once and linked once. No node is revisited.

Space complexity

O(1)

The merge is in place: it re-links existing nodes. Only the dummy and a couple of pointers are extra.

Inputs & edge cases

Live animation — compare the two heads, splice the smaller onto the result

list A / pointer a list B / pointer b merged result already consumed

List A

List B

Compare heads

Merged result

a = — b = — picked = — merged = —

Step — of —

a head

—

list A

b head

—

list B

picked

—

smaller head

merged len

—

nodes linked

Select an input and press Play to start.

✓ Done

Speed Medium

Step-by-step table

Step	a head	b head	Compare	Picked	Merged so far

C++ implementation

merge_two_lists.cpp

#include <bits/stdc++.h>
using namespace std;

struct ListNode { int val; ListNode* next; };

// Merge two sorted lists by splicing the smaller head each step.
ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
    ListNode dummy;              // sentinel: no empty-result special case
    ListNode* tail = &dummy;

    while (a && b) {
        if (a->val <= b->val) {   // <= keeps the merge stable
            tail->next = a; a = a->next;
        } else {
            tail->next = b; b = b->next;
        }
        tail = tail->next;
    }
    tail->next = a ? a : b;       // attach the leftover sorted tail
    return dummy.next;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars