Merge Two Sorted Linked Lists

time: O(n + m)
space: O(1)
tags: linked-lists · two-pointer

in the wild Merging two sorted sensor streams (time-stamped) into one ordered timeline.

Problem

Given the heads of two sorted linked lists, merge them into a single sorted list by splicing together their existing nodes. Return the head of the merged list. Don't allocate new nodes.

Examples

[1, 3, 5] + [2, 4, 6] → [1, 2, 3, 4, 5, 6]
[1, 1, 1] + [2, 2, 2] → [1, 1, 1, 2, 2, 2]
[] + [1, 2] → [1, 2]
[] + [] → []

Why this is the canonical two-pointer-on-linked-lists problem

The "merge" step of merge sort, applied to linked lists. Two pointers, one in each list, advance whichever points to the smaller value. Splice it onto the growing tail. Repeat until one list is exhausted; attach the remainder of the other.

The elegance is that no allocation happens. Linked lists are perfect for splicing — unlike arrays where merging requires copying every element, here we just redirect next pointers.

The classic trick is a dummy head node. Without it, the first comparison needs special handling (which is the new head, a or b?). With a dummy, you always have a "previous" to attach to, and at the end you return dummy.next. Clean code.

Hints

Hint 1 — splice, don't allocate

You don't need to create new nodes. The nodes already exist in a and b; you just need to rearrange their next pointers so they form one sorted chain.

Hint 2 — dummy head pattern

Start with a sentinel "dummy" node — its next will become the real head once the merge is done. Maintain a tail pointer that always points at the last node of your growing merged list.

dummy = Node()
tail = dummy
while a and 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 or b   # attach the non-empty remainder
return dummy.next

Solution

class Node:
    def __init__(self, val: int, nxt: "Node | None" = None):
        self.val, self.next = val, nxt

def merge(a: Node | None, b: Node | None) -> Node | None:
    dummy = Node(0)
    tail = dummy
    while a and 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 or b   # attach whichever still has nodes
    return dummy.next

# Helpers
def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def collect(head):
    out = []
    while head: out.append(head.val); head = head.next
    return out

cases = [
    ([1, 3, 5],  [2, 4, 6]),    # interleaved
    ([],         [1, 2, 3]),    # one empty
    ([1, 2, 3],  []),
    ([],         []),           # both empty
    ([1, 1, 1],  [2, 2, 2]),    # duplicates
]
for a, b in cases:
    got = collect(merge(build(a), build(b)))
    expected = sorted(a + b)
    mark = "✓" if got == expected else "✗"
    print(f"{mark} merge({a}, {b}) = {got}")

class Node {
  constructor(val, next = null) { this.val = val; this.next = next; }
}

function merge(a, b) {
  const dummy = new Node(0);
  let tail = dummy;
  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 || b;
  return dummy.next;
}

const build = (vs) => vs.reduceRight((tail, v) => new Node(v, tail), null);
const collect = (head) => {
  const out = [];
  while (head) { out.push(head.val); head = head.next; }
  return out;
};

const cases = [
  [[1, 3, 5],  [2, 4, 6]],
  [[],         [1, 2, 3]],
  [[1, 2, 3],  []],
  [[],         []],
  [[1, 1, 1],  [2, 2, 2]],
];
for (const [a, b] of cases) {
  const got = collect(merge(build(a), build(b)));
  const expected = [...a, ...b].sort((x, y) => x - y);
  const ok = JSON.stringify(got) === JSON.stringify(expected);
  console.log(`${ok ? "✓" : "✗"} merge(${JSON.stringify(a)}, ${JSON.stringify(b)}) = ${JSON.stringify(got)}`);
}

pub struct Node { pub val: i32, pub next: Option<Box<Node>> }

pub fn merge(mut a: Option<Box<Node>>, mut b: Option<Box<Node>>) -> Option<Box<Node>> {
    let mut dummy = Box::new(Node { val: 0, next: None });
    let mut tail = &mut dummy;
    loop {
        match (a.as_ref(), b.as_ref()) {
            (None, None) => break,
            (Some(_), None) => { tail.next = a; break; }
            (None, Some(_)) => { tail.next = b; break; }
            (Some(an), Some(bn)) => {
                if an.val <= bn.val {
                    let mut node = a.take().unwrap();
                    a = node.next.take();
                    tail.next = Some(node);
                } else {
                    let mut node = b.take().unwrap();
                    b = node.next.take();
                    tail.next = Some(node);
                }
                tail = tail.next.as_mut().unwrap();
            }
        }
    }
    dummy.next
}

fn build(values: &[i32]) -> Option<Box<Node>> {
    let mut head = None;
    for &v in values.iter().rev() { head = Some(Box::new(Node { val: v, next: head })); }
    head
}
fn collect(mut head: Option<Box<Node>>) -> Vec<i32> {
    let mut out = vec![];
    while let Some(n) = head { out.push(n.val); head = n.next; }
    out
}

fn main() {
    let cases: &[(&[i32], &[i32])] = &[
        (&[1,3,5], &[2,4,6]),
        (&[],      &[1,2,3]),
        (&[1,2,3], &[]),
        (&[],      &[]),
        (&[1,1,1], &[2,2,2]),
    ];
    for (a, b) in cases {
        let got = collect(merge(build(a), build(b)));
        let mut expected: Vec<i32> = a.iter().chain(b.iter()).copied().collect();
        expected.sort();
        let mark = if got == expected { "✓" } else { "✗" };
        println!("{mark} merge({:?}, {:?}) = {:?}", a, b, got);
    }
}

#include <iostream>
#include <vector>
#include <memory>
#include <algorithm>

struct Node {
    int val;
    std::unique_ptr<Node> next;
    Node(int v, std::unique_ptr<Node> nx = nullptr) : val(v), next(std::move(nx)) {}
};

std::unique_ptr<Node> merge(std::unique_ptr<Node> a, std::unique_ptr<Node> b) {
    auto dummy = std::make_unique<Node>(0);
    Node* tail = dummy.get();
    while (a && b) {
        if (a->val <= b->val) {
            auto nxt = std::move(a->next);
            tail->next = std::move(a);
            a = std::move(nxt);
        } else {
            auto nxt = std::move(b->next);
            tail->next = std::move(b);
            b = std::move(nxt);
        }
        tail = tail->next.get();
    }
    tail->next = a ? std::move(a) : std::move(b);
    return std::move(dummy->next);
}

std::unique_ptr<Node> build(const std::vector<int>& vs) {
    std::unique_ptr<Node> head;
    for (auto it = vs.rbegin(); it != vs.rend(); ++it)
        head = std::make_unique<Node>(*it, std::move(head));
    return head;
}
std::vector<int> collect(std::unique_ptr<Node> head) {
    std::vector<int> out;
    while (head) { out.push_back(head->val); head = std::move(head->next); }
    return out;
}

int main() {
    std::vector<std::pair<std::vector<int>, std::vector<int>>> cases = {
        {{1,3,5},{2,4,6}}, {{},{1,2,3}}, {{1,2,3},{}}, {{},{}}, {{1,1,1},{2,2,2}},
    };
    for (auto& [a, b] : cases) {
        auto got = collect(merge(build(a), build(b)));
        std::vector<int> expected(a); for (int x : b) expected.push_back(x);
        std::sort(expected.begin(), expected.end());
        std::cout << (got == expected ? "✓" : "✗") << " merge(.., ..) = {";
        for (size_t i = 0; i < got.size(); ++i) std::cout << got[i] << (i + 1 < got.size() ? "," : "");
        std::cout << "}\n";
    }
}

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int val; struct Node* next; } Node;

Node* merge(Node* a, Node* b) {
    Node dummy = {0, NULL};
    Node* tail = &dummy;
    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;
    return dummy.next;
}

Node* build(const int* vs, int n) {
    Node* head = NULL;
    for (int i = n - 1; i >= 0; i--) {
        Node* node = malloc(sizeof(Node));
        node->val = vs[i]; node->next = head;
        head = node;
    }
    return head;
}
static void print_list(Node* head) {
    printf("{");
    for (Node* p = head; p; p = p->next) printf("%d%s", p->val, p->next ? "," : "");
    printf("}");
}
static void free_list(Node* head) {
    while (head) { Node* n = head->next; free(head); head = n; }
}

int main(void) {
    int a1[] = {1,3,5}, b1[] = {2,4,6};
    Node* r1 = merge(build(a1, 3), build(b1, 3));
    printf("✓ merge({1,3,5}, {2,4,6}) = "); print_list(r1); printf("\n"); free_list(r1);

    int b2[] = {1,2,3};
    Node* r2 = merge(NULL, build(b2, 3));
    printf("✓ merge({}, {1,2,3}) = "); print_list(r2); printf("\n"); free_list(r2);

    int a3[] = {1,2,3};
    Node* r3 = merge(build(a3, 3), NULL);
    printf("✓ merge({1,2,3}, {}) = "); print_list(r3); printf("\n"); free_list(r3);

    Node* r4 = merge(NULL, NULL);
    printf("✓ merge({}, {}) = "); print_list(r4); printf("\n");

    int a5[] = {1,1,1}, b5[] = {2,2,2};
    Node* r5 = merge(build(a5, 3), build(b5, 3));
    printf("✓ merge({1,1,1}, {2,2,2}) = "); print_list(r5); printf("\n"); free_list(r5);
    return 0;
}

idle

The algorithm is identical across all five — splice, don't allocate. The differences are entirely about who handles memory: Python/JS lean on GC, Rust uses Option<Box<Node>> with .take(), C++ uses std::unique_ptr with std::move, and C does manual malloc/free. Same dance, five flavors of ceremony.

Complexity

Time: O(n + m) — each node from either list is touched exactly once.
Space: O(1) — just the dummy node and the tail pointer. No new allocations beyond the sentinel.
vs arrays: The array equivalent is also O(n + m) time but requires O(n + m) destination space (you can't merge in-place into either input array). Linked lists splice in O(1) space.

In the wild

Merge sort. The bottom-up linked-list merge sort uses this as its merge step. Sort n items in O(n log n) time and O(log n) recursion-stack space (vs O(n) for array merge sort).
Streaming sensor fusion. Two time-stamped sensor feeds, both already in temporal order — merge into one timeline for processing.
Log file merging. Combining two sorted log files (sorted by timestamp) into one master log for an ops investigation.
Database query plans. Index-based "merge join" between two sorted indexes is structurally the same operation.

Variations

Merge K sorted lists. Generalizes to a min-heap of K head pointers (next problem in the heap lesson). O(n log k) total.
Merge two sorted arrays in-place. If the destination array has room for both (a-followed-by-zeros pattern), you can merge in-place by walking backward from the end.
Detect duplicates while merging. Skip identical values from one input to deduplicate as you go.