Merge Two Sorted Lists

LINKED LIST · EASY

Builds on Day 15: Linked Lists

This problem is a direct test of pointer manipulation: reading, comparing, and re-pointing .next on existing nodes; read that lesson first if singly-linked list traversal is still a new idea.

The problem

You’re given the heads of two singly-linked lists, list1 and list2, each already sorted in ascending order. Merge them into a single sorted list and return its head. The catch that makes this a real linked-list exercise, not just an array problem in disguise: the merge has to happen by splicing together the existing nodes — re-pointing their .next references — not by creating brand-new nodes to hold the same values. For example, list1 = [1,2,4] and list2 = [1,3,4] merge into [1,1,2,3,4,4]. Either input can be empty: list1 = [], list2 = [] returns [], and list1 = [], list2 = [0] returns [0] — list2 untouched, just handed back as-is.

LeetCode: Merge Two Sorted Lists

Solution 1: Brute force — extract, sort, rebuild

The straightforward approach: walk both lists and dump every value into one plain JS array, sort that array numerically, then build an entirely new linked list from the sorted array, allocating a fresh node for every value. This is completely correct, but it’s honest to call it “brute force” for two specific reasons: it runs a full comparison sort on data that was already sorted on both sides — genuinely unnecessary work — and it throws away the original nodes entirely instead of reusing them, allocating n + m new node objects for values that already had perfectly good nodes sitting in memory.

list1 = [1, 2, 4], list2 = [1, 3, 4] — extract both into an array, sort it, rebuild from scratch

Press Play or Step to begin.

Step 0 / 0

▶ Play⏭ Step↺ Reset

The code

function mergeTwoListsBruteForce(list1, list2) {
  const values = [];

  let cur = list1;
  while (cur) { values.push(cur.val); cur = cur.next; }
  cur = list2;
  while (cur) { values.push(cur.val); cur = cur.next; }

  values.sort((a, b) => a - b);

  let head = null, tail = null;
  for (const v of values) {
    const node = { val: v, next: null };
    if (!head) { head = node; tail = node; }
    else { tail.next = node; tail = node; }
  }
  return head;
}

Line by line:

• values collects every value from both lists into one plain array — the two while loops just walk .next until they hit null, exactly like reading any singly-linked list.
• values.sort((a, b) => a - b) — the numeric comparator matters: Array.prototype.sort defaults to comparing elements as strings, so without it [1, 2, 10] would sort to [1, 10, 2]. This line is also the “unnecessary” part of the brute force — both inputs were already sorted, so this is a full O(k log k) sort applied to data that didn’t need reordering, only interleaving.
• The build loop allocates a fresh { val, next: null } object for every value — none of the original list1/list2 node objects are reused. A head/tail pair (rather than always walking from head to append) keeps each append O(1) instead of O(k).
• Returning head (which stays null if values was empty) correctly handles the list1 = [], list2 = [] case.

Complexity

Time	Space	Approach
O((n+m) log(n+m))	O(n+m)	Extract into an array, sort, rebuild with brand-new nodes

Solution 2: Optimal — two-pointer merge, splice in place

Both lists are already sorted — the brute force’s sort step is solving a problem that doesn’t exist. The optimal approach exploits that directly: walk both lists with two pointers at the same time, and at every step, compare the two current values and re-point an existing node’s .next to whichever one is smaller — no new memory allocated, ever. A dummy/sentinel head node makes the bookkeeping clean: instead of special-casing “is this the very first node of the result?”, every real node (from either input) gets spliced onto tail.next the exact same way, and the real answer is just dummy.next at the end.

The one place it’s easy to get sloppy: once either pointer runs off the end of its list, the other list’s remaining nodes are already sorted relative to each other — there’s no need to keep comparing them one at a time. Splice the entire remainder directly onto tail.next in a single assignment and stop.

list1 = [1, 2, 4], list2 = [1, 3, 4] — two-pointer splice with no new nodes

Press Play or Step to begin.

Step 0 / 0

▶ Play⏭ Step↺ Reset

The code

function mergeTwoListsOptimal(list1, list2) {
  const dummy = { val: 0, next: null };
  let tail = dummy;
  let p1 = list1, p2 = list2;

  while (p1 && p2) {
    if (p1.val <= p2.val) {
      tail.next = p1;
      p1 = p1.next;
    } else {
      tail.next = p2;
      p2 = p2.next;
    }
    tail = tail.next;
  }

  // One list is exhausted — the other's remaining nodes are already
  // sorted relative to each other, so splice the whole remainder at once.
  tail.next = p1 ? p1 : p2;

  return dummy.next;
}

Line by line:

• dummy is a throwaway sentinel node — its own val is never used. It exists purely so tail always has something to attach to, even before the first real node is spliced in, avoiding a special case for “is this the first node of the result?”
• p1.val <= p2.val uses <=, not < — when values tie, list1’s node is spliced first. Either choice is valid (both produce a correctly sorted merge), but being consistent about it keeps the merge stable and predictable.
• tail.next = p1; is the entire splice: no new object is created, an existing node is simply re-pointed onto the result chain. p1 = p1.next then advances that pointer using the node’s original .next — read before it gets overwritten again on some future iteration.
• tail = tail.next; moves the tail pointer forward to the node that was just spliced on, so the next splice attaches after it.
• tail.next = p1 ? p1 : p2; is the remainder shortcut: whichever pointer is still non-null holds an already-sorted-internally chain, so one assignment splices all of it on at once — no loop needed for the tail end.
• return dummy.next; — the sentinel itself is never part of the answer; its .next is wherever the first real node landed. If both inputs were empty, dummy.next is still null, correctly matching the empty-list case.

Complexity

Time	Space	Approach
O(n+m)	O(1) extra	Two-pointer merge, splicing existing nodes in place

Complexity comparison

Solution	Time	Space
Brute force (extract, sort, rebuild)	O((n+m) log(n+m))	O(n+m)
Optimal (two-pointer splice)	O(n+m)	O(1) extra

This is a rarer case on this site where BOTH dimensions genuinely improve, not just one. Time drops from O((n+m) log(n+m)) to O(n+m) because the optimal solution never re-sorts data that was already sorted — it only needs to interleave the two lists once. Space drops from O(n+m) to O(1) extra because splicing reuses the existing node objects instead of allocating n+m new ones (the O(n+m) output list itself is the answer, not “extra” space beyond what the problem already asks the function to return).

Interview corner

Q: Why does using a dummy/sentinel head node actually simplify this problem, instead of just being a stylistic choice?

• Without it, the very first splice is a special case: there’s no existing tail to attach to yet, so the code would need an if (!head) head = winner; else tail.next = winner; branch just for that one moment.
• With dummy, tail always points at something real from the first line of the function onward — the first splice (tail.next = p1, where tail is dummy) is handled by the exact same code path as every later splice. No branch, no asymmetry.
• It also makes the empty/empty case fall out for free: the while loop never runs, the remainder line assigns null, and dummy.next is correctly still null — no explicit “handle the empty case” logic needed anywhere.

Q: The remainder step does tail.next = p1 ? p1 : p2; in one line instead of looping through the leftover nodes one at a time. Why is that safe?

• By the time the main while loop exits, at least one of p1 / p2 is null — that list is fully spliced in. The other pointer still references a valid chain of nodes that were never touched.
• That remaining chain is still internally sorted (it’s a suffix of an input list that was sorted from the start) and every value in it is >= everything already spliced onto tail — merging never skips ahead, so whatever’s left in one list can’t be smaller than what the other list already contributed up to this point.
• Because the remaining nodes already point to each other correctly via their own .next chain, attaching just the first one (tail.next = p1, say) transitively brings the entire rest of the chain along — there’s nothing left to compare.

↳ Common follow-up: “What if you forgot this shortcut and just let the while loop keep running?” It wouldn’t — the loop condition is p1 && p2, so it necessarily stops the instant either pointer goes null. Forgetting the remainder line entirely (not just the shortcut, but omitting it outright) would silently drop the rest of the longer list from the answer.

Q: This solution splices existing nodes rather than copying values into new ones. What’s the practical risk of that, if the caller still holds a reference to one of the original list variables after calling mergeTwoListsOptimal?

• The nodes aren’t copied — they’re the exact same objects, just with their .next fields reassigned. If a caller kept a separate variable pointing at, say, list1’s head, that variable now sits inside a list whose downstream shape has been rewritten out from under it.
• Walking from that old reference no longer reproduces the original list1 — its later nodes may now belong to segments interleaved with list2’s nodes, because .next was mutated in place.
• This is the direct real-world consequence of “splice, don’t copy”: it’s what makes the optimal solution O(1) extra space, but it also means the caller’s original list1/list2 references are no longer safe to use as if they were untouched — a tradeoff worth stating out loud in an interview, not just assuming.

Q: Trick question — since splicing means two variables can end up pointing at the exact same node object, what does this log?

const node = { val: 1, next: null };
const list1 = node; // caller still holds this reference

const dummy = { val: 0, next: null };
dummy.next = node;       // splice — same object, not a copy
dummy.next.val = 999;    // mutate through the merged-list path

console.log(list1.val);

• Answer: 999, not 1. node.js verified.
• list1 and dummy.next aren’t two copies of the same data — they’re two variables holding a reference to the exact same object in memory. Mutating a property through one reference (dummy.next.val = 999) is visible through every other reference to that same object, including list1.
• This is exactly the mechanism the optimal solution relies on for splicing to work at all (re-pointing .next on a shared node reference IS the algorithm) — and exactly why it’s not safe to assume an original list variable is untouched after this function runs, per the interview question above.

⚠ Trap: this has nothing to do with const — const node = ... only prevents reassigning what node points to, it does nothing to freeze the object’s own properties. const objects are still fully mutable unless explicitly frozen with Object.freeze().

Quiz

Quiz: 1. What problem does the dummy/sentinel head node actually solve?

It removes the need for a special case handling the very first node spliced onto the result

A dummy/sentinel head means tail always has something real to attach to, even before the first node is spliced — so the first splice uses the exact same code path as every later one, with no special-cased branch.

Quiz: 2. What is the honest complexity improvement of the optimal two-pointer splice over the extract-sort-rebuild brute force?

Both improve: time drops the unnecessary log factor, and space drops from O(n+m) to O(1) extra

Time drops from O((n+m) log(n+m)) to O(n+m) because the optimal solution never re-sorts already-sorted data — and space drops from O(n+m) to O(1) extra because splicing reuses existing nodes instead of allocating new ones. Both dimensions genuinely improve here.

Quiz: 3. Why can the remainder be spliced with one assignment (tail.next = p1 ? p1 : p2) instead of looping node by node?

The remaining chain is already sorted and already linked internally, so attaching its first node brings the whole rest of the chain along automatically

The remaining chain is already sorted and already linked internally, so attaching its first node brings the whole rest of the chain along automatically.

Quiz: 4. After calling the optimal solution, what actually happened to the original list1 and list2 node objects?

Nothing was copied — the same node objects were reused, with their .next fields re-pointed in place

Splicing reuses the original node objects and only reassigns .next — it never allocates new nodes or copies values. That’s exactly what makes it O(1) extra space, but it also means old references to list1/list2 may now traverse a mutated, interleaved chain.

Quiz: 5. const node = { val: 1, next: null }; const list1 = node; dummy.next = node; dummy.next.val = 999; console.log(list1.val); — what does this log?

999 — list1 and dummy.next point to the same object, so the mutation is visible through both

list1 and dummy.next are two variables referencing the exact same object — mutating a property through one reference (dummy.next.val = 999) is visible through every other reference to that same object, including list1. const only prevents reassigning what the variable points to, it doesn’t freeze the object’s properties.