#19 · Linked List

Merge Two Sorted Lists

Merge two sorted linked lists into one sorted list by splicing together the nodes of the two lists, and return its head.

EasyLeetCode

Current node
Link just rewired
Done / in result
Marked
Rejected
Dummy head

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Dummy (sentinel) head

A throwaway node placed in front of the result so that "attach to the end of the result" is the same operation for the first node as for every other one. Without it the first node is a special case with its own branch.

Memory layout

One extra node (or a stack-allocated one). It is never part of the returned list: you return dummy.next.

Operation	Cost
attach node at tail	O(1)
extra space	O(1)

Two-pointer merge on sorted sequences

Both lists are sorted, so the next output element is always the smaller of the two current heads. One pointer per list, advancing only the one that was taken, never goes backwards.

Memory layout

Two references (a, b) and the tail reference; nodes are re-linked in place, so nothing is copied.

Operation	Cost
merge	O(n + m) time
auxiliary space	O(1) iterative, O(n + m) recursive

Why it fits

Sortedness means the smallest remaining element is always at one of the two heads, so a greedy comparison of just two nodes decides every output position.
Linked lists can splice an existing node after the tail in O(1), so the merge reuses the original nodes and needs no copying or shifting (unlike merging arrays).
A dummy head removes the "is the result still empty?" branch, which is where most bugs in this problem live.

Why alternatives degrade

Dump both lists into an array and sort:: Ignores that the inputs are sorted: O((n+m) log(n+m)) time and O(n+m) space, plus new nodes, versus O(n+m) time and O(1) space.
Insert each node of list2 into list1:: Each insertion may scan list1 from the start: O(n·m) worst case.
Merging arrays by shifting:: Inserting in the middle of an array is O(n); a linked list splices in O(1).

Four approaches, from naive to production

1 · beginner

Collect, sort, rebuild

time O((n+m) log(n+m))space O(n+m)

Copy every value into an array, sort it, then build a brand new list from the sorted values.

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    vector<int> vals;
    for (ListNode* n = list1; n; n = n->next) vals.push_back(n->val);
    for (ListNode* n = list2; n; n = n->next) vals.push_back(n->val);
    sort(vals.begin(), vals.end());
    ListNode* dummy = new ListNode(0);
    ListNode* tail = dummy;
    for (int v : vals) {
        tail->next = new ListNode(v);
        tail = tail->next;
    }
    return dummy->next;
}

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode n = list1; n != null; n = n.next) vals.add(n.val);
    for (ListNode n = list2; n != null; n = n.next) vals.add(n.val);
    Collections.sort(vals);
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    for (int v : vals) {
        tail.next = new ListNode(v);
        tail = tail.next;
    }
    return dummy.next;
}

def merge_two_lists(list1, list2):
    vals = []
    n = list1
    while n:
        vals.append(n.val)
        n = n.next
    n = list2
    while n:
        vals.append(n.val)
        n = n.next
    vals.sort()
    dummy = ListNode(0)
    tail = dummy
    for v in vals:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  const vals: number[] = [];
  for (let n = list1; n; n = n.next) vals.push(n.val);
  for (let n = list2; n; n = n.next) vals.push(n.val);
  vals.sort((a, b) => a - b);
  const dummy = new ListNode(0);
  let tail = dummy;
  for (const v of vals) {
    tail.next = new ListNode(v);
    tail = tail.next;
  }
  return dummy.next;
}

Flaws & bottlenecks

Throws away the fact that both inputs are already sorted, paying an extra log factor.
Allocates n+m new nodes plus the array; the problem asks to splice the existing nodes.
Two passes over the data plus a sort: poor cache behavior and more memory churn.

Interviewer cross-questions

Can you exploit the fact that the lists are sorted?

Say: Yes: compare the two heads and always take the smaller. That is a linear merge, the same merge step used by merge sort.

Is the node identity preserved?

Say: No. New nodes are created, so any outside references to the original nodes are no longer part of the result. The problem asks for the original nodes to be spliced together.

What if the lists are huge?

Say: This approach needs the whole data in memory at once. A streaming merge holds only two heads.

2 · intermediate

Recursion

time O(n + m)space O(n + m)

Whichever head is smaller becomes the head of the result; its next is the merge of the remaining nodes. If one list is empty, return the other.

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    if (!list1) return list2;
    if (!list2) return list1;
    if (list1->val <= list2->val) {
        list1->next = mergeTwoLists(list1->next, list2);
        return list1;
    }
    list2->next = mergeTwoLists(list1, list2->next);
    return list2;
}

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null) return list2;
    if (list2 == null) return list1;
    if (list1.val <= list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    }
    list2.next = mergeTwoLists(list1, list2.next);
    return list2;
}

def merge_two_lists(list1, list2):
    if not list1:
        return list2
    if not list2:
        return list1
    if list1.val <= list2.val:
        list1.next = merge_two_lists(list1.next, list2)
        return list1
    list2.next = merge_two_lists(list1, list2.next)
    return list2

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  if (!list1) return list2;
  if (!list2) return list1;
  if (list1.val <= list2.val) {
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  }
  list2.next = mergeTwoLists(list1, list2.next);
  return list2;
}

Flaws & bottlenecks

The call stack grows to n+m frames, which can overflow for long lists.
The linking happens on the way back, so the code reads as magic if you have not traced it.
Each frame is pure overhead for what is a simple loop.

Interviewer cross-questions

What is the recursion depth?

Say: Up to n+m: one frame per node taken, since each call consumes one node. That is O(n+m) stack space, so lists of ~10⁵ nodes can overflow.

Why are the base cases enough?

Say: When one list runs out, the other is already sorted and can be attached whole. So only the two empty-list cases need handling.

How do you get rid of the stack?

Say: Use a dummy head and a tail pointer, and replace each recursive call with "attach the smaller node after tail and advance": the iterative approach.

3 · advanced

Iterative dummy head + tail

time O(n + m)space O(1)

Keep a tail pointer on a dummy head. While both lists have nodes, link the smaller head after tail and advance. Finally attach the leftover list.

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    ListNode* a = list1;
    ListNode* b = list2;
    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;
}

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    ListNode a = list1;
    ListNode b = list2;
    while (a != null && b != null) {
        if (a.val <= b.val) {
            tail.next = a;
            a = a.next;
        } else {
            tail.next = b;
            b = b.next;
        }
        tail = tail.next;
    }
    tail.next = a != null ? a : b;
    return dummy.next;
}

def merge_two_lists(list1, list2):
    dummy = ListNode(0)
    tail = dummy
    a = list1
    b = list2
    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
    return dummy.next

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);
  let tail = dummy;
  let a = list1;
  let b = list2;
  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;
}

Flaws & bottlenecks

Relinks nodes in place, so the input lists are destroyed (they now share nodes with the result).
One pointer write per node even when long runs of one list come first.
The tie case (a.val == b.val) must consistently pick the same list to keep the merge stable.

Interviewer cross-questions

Why is the dummy node worth it?

Say: Without it you must handle "result is empty" separately for the very first node. With it, tail.next = x works for every node, and the answer is dummy.next.

Is the merge stable?

Say: Yes, because ties take from list1 first (a.val <= b.val), so equal elements keep their original relative order.

What is the complexity if one list is much longer?

Say: Still O(n+m), but you may pay for walking the long list one node at a time. The expert version attaches a leftover run in one step, and a run splice speeds up inputs with long runs.

4 · expert

Splice whole runs at once

time O(n + m)space O(1)

Same dummy/tail merge, but when a list takes the lead, keep following its nodes while they are still ≤ the other head, and attach the whole run with one write.

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    ListNode* a = list1;
    ListNode* b = list2;
    while (a && b) {
        if (b->val < a->val) swap(a, b);
        tail->next = a;
        while (a->next && a->next->val <= b->val) a = a->next;
        tail = a;
        a = a->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    ListNode a = list1;
    ListNode b = list2;
    while (a != null && b != null) {
        if (b.val < a.val) { ListNode t = a; a = b; b = t; }
        tail.next = a;
        while (a.next != null && a.next.val <= b.val) a = a.next;
        tail = a;
        a = a.next;
    }
    tail.next = a != null ? a : b;
    return dummy.next;
}

def merge_two_lists(list1, list2):
    dummy = ListNode(0)
    tail = dummy
    a = list1
    b = list2
    while a and b:
        if b.val < a.val:
            a, b = b, a
        tail.next = a
        while a.next and a.next.val <= b.val:
            a = a.next
        tail = a
        a = a.next
    tail.next = a or b
    return dummy.next

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);
  let tail = dummy;
  let a = list1;
  let b = list2;
  while (a && b) {
    if (b.val < a.val) [a, b] = [b, a];
    tail.next = a;
    while (a.next && a.next.val <= b.val) a = a.next;
    tail = a;
    a = a.next;
  }
  tail.next = a ?? b;
  return dummy.next;
}

Flaws & bottlenecks

Extra comparisons inside the run loop make it slower than the plain loop on interleaved inputs (alternating nodes), where every run has length 1.
Not stable across lists: after a swap the list2 run may pass equal values from list1. Fine for numbers, wrong if equal keys carry data.
More complex invariants than the simple loop, so harder to review and debug.

Interviewer cross-questions

When does this win?

Say: When the inputs have long runs (for example merging a big sorted list with a few new items). The number of pointer writes becomes the number of runs, and the leftover tail is attached without being visited.

Why is the swap needed?

Say: It keeps a pointing at the list with the smaller head, so the rest of the loop is written only once instead of twice (one branch per list).

Would you use this in production?

Say: Only if profiling shows the merge is hot and data has long runs. This idea is the "galloping" mode in Timsort, which switches to it only when one side keeps winning.

Synchronized code walkthrough

Showing: Collect, sort, rebuild — shares the player above; click any step to jump.

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    vector<int> vals;
    for (ListNode* n = list1; n; n = n->next) vals.push_back(n->val);
    for (ListNode* n = list2; n; n = n->next) vals.push_back(n->val);
    sort(vals.begin(), vals.end());
    ListNode* dummy = new ListNode(0);
    ListNode* tail = dummy;
    for (int v : vals) {
        tail->next = new ListNode(v);
        tail = tail->next;
    }
    return dummy->next;
}

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode n = list1; n != null; n = n.next) vals.add(n.val);
    for (ListNode n = list2; n != null; n = n.next) vals.add(n.val);
    Collections.sort(vals);
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    for (int v : vals) {
        tail.next = new ListNode(v);
        tail = tail.next;
    }
    return dummy.next;
}

def merge_two_lists(list1, list2):
    vals = []
    n = list1
    while n:
        vals.append(n.val)
        n = n.next
    n = list2
    while n:
        vals.append(n.val)
        n = n.next
    vals.sort()
    dummy = ListNode(0)
    tail = dummy
    for v in vals:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  const vals: number[] = [];
  for (let n = list1; n; n = n.next) vals.push(n.val);
  for (let n = list2; n; n = n.next) vals.push(n.val);
  vals.sort((a, b) => a - b);
  const dummy = new ListNode(0);
  let tail = dummy;
  for (const v of vals) {
    tail.next = new ListNode(v);
    tail = tail.next;
  }
  return dummy.next;
}

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    if (!list1) return list2;
    if (!list2) return list1;
    if (list1->val <= list2->val) {
        list1->next = mergeTwoLists(list1->next, list2);
        return list1;
    }
    list2->next = mergeTwoLists(list1, list2->next);
    return list2;
}

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null) return list2;
    if (list2 == null) return list1;
    if (list1.val <= list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    }
    list2.next = mergeTwoLists(list1, list2.next);
    return list2;
}

def merge_two_lists(list1, list2):
    if not list1:
        return list2
    if not list2:
        return list1
    if list1.val <= list2.val:
        list1.next = merge_two_lists(list1.next, list2)
        return list1
    list2.next = merge_two_lists(list1, list2.next)
    return list2

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  if (!list1) return list2;
  if (!list2) return list1;
  if (list1.val <= list2.val) {
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  }
  list2.next = mergeTwoLists(list1, list2.next);
  return list2;
}

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    ListNode* a = list1;
    ListNode* b = list2;
    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;
}

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    ListNode a = list1;
    ListNode b = list2;
    while (a != null && b != null) {
        if (a.val <= b.val) {
            tail.next = a;
            a = a.next;
        } else {
            tail.next = b;
            b = b.next;
        }
        tail = tail.next;
    }
    tail.next = a != null ? a : b;
    return dummy.next;
}

def merge_two_lists(list1, list2):
    dummy = ListNode(0)
    tail = dummy
    a = list1
    b = list2
    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
    return dummy.next

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);
  let tail = dummy;
  let a = list1;
  let b = list2;
  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;
}

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    ListNode* a = list1;
    ListNode* b = list2;
    while (a && b) {
        if (b->val < a->val) swap(a, b);
        tail->next = a;
        while (a->next && a->next->val <= b->val) a = a->next;
        tail = a;
        a = a->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    ListNode a = list1;
    ListNode b = list2;
    while (a != null && b != null) {
        if (b.val < a.val) { ListNode t = a; a = b; b = t; }
        tail.next = a;
        while (a.next != null && a.next.val <= b.val) a = a.next;
        tail = a;
        a = a.next;
    }
    tail.next = a != null ? a : b;
    return dummy.next;
}

def merge_two_lists(list1, list2):
    dummy = ListNode(0)
    tail = dummy
    a = list1
    b = list2
    while a and b:
        if b.val < a.val:
            a, b = b, a
        tail.next = a
        while a.next and a.next.val <= b.val:
            a = a.next
        tail = a
        a = a.next
    tail.next = a or b
    return dummy.next

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);
  let tail = dummy;
  let a = list1;
  let b = list2;
  while (a && b) {
    if (b.val < a.val) [a, b] = [b, a];
    tail.next = a;
    while (a.next && a.next.val <= b.val) a = a.next;
    tail = a;
    a = a.next;
  }
  tail.next = a ?? b;
  return dummy.next;
}