Skip to main content

3. Merge Two Sorted Lists

easyAsked at Vercel

Merge two sorted linked lists into one sorted list by splicing nodes together. Vercel asks this as the building block of their log-merge sub-question for edge-function telemetry — same pattern as merging sorted per-region access logs.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-10)— Vercel onsite warm-up; often followed by 'merge k sorted edge logs' as a heap follow-up.
  • LeetCode Discuss (2026-Q1)— Cited as Vercel platform-engineer screen #1.

Problem

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

Constraints

  • The number of nodes in both lists is in the range [0, 50].
  • -100 <= Node.val <= 100
  • Both list1 and list2 are sorted in non-decreasing order.

Examples

Example 1

Input
list1 = [1,2,4], list2 = [1,3,4]
Output
[1,1,2,3,4,4]

Example 2

Input
list1 = [], list2 = []
Output
[]

Approaches

1. Convert to array, sort, rebuild

Dump both lists into an array, sort, rebuild a new linked list from the sorted array.

Time
O((m+n) log(m+n))
Space
O(m+n)
function mergeTwoLists(l1, l2) {
  const arr = [];
  while (l1) { arr.push(l1.val); l1 = l1.next; }
  while (l2) { arr.push(l2.val); l2 = l2.next; }
  arr.sort((a,b) => a - b);
  const dummy = { next: null };
  let cur = dummy;
  for (const v of arr) { cur.next = { val: v, next: null }; cur = cur.next; }
  return dummy.next;
}

Tradeoff: Throws away the fact that the inputs are already sorted. O(n log n) when O(n) is possible.

2. Two-pointer splice with dummy head (optimal)

Use a dummy node. Advance whichever pointer has the smaller current value; splice that node into the result. Attach the leftover tail when one list runs out.

Time
O(m+n)
Space
O(1) extra
function mergeTwoLists(l1, l2) {
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) {
      tail.next = l1;
      l1 = l1.next;
    } else {
      tail.next = l2;
      l2 = l2.next;
    }
    tail = tail.next;
  }
  tail.next = l1 || l2;
  return dummy.next;
}

Tradeoff: O(m+n) single pass, O(1) extra space because we splice existing nodes instead of allocating. The dummy head removes the awkward 'is this the first node' branch.

Vercel-specific tips

Vercel interviewers look for the dummy-head pattern and the in-place splice (no new allocations). Bonus signal: noticing that one of the inputs may be null and handling it without a separate guard. They also love when you tie this to a real systems analogy like 'this is exactly how I'd merge two sorted edge-access-log streams from neighboring regions before fan-in.'

Common mistakes

  • Allocating new nodes instead of splicing — works but wastes memory and signals you missed the in-place trick.
  • Forgetting `tail.next = l1 || l2` at the end — leaves the merged list truncated when one side is longer.
  • Initializing `tail = dummy.next` instead of `tail = dummy` — breaks the first append.

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

  • Merge k sorted lists (LC 23, hard) — heap or divide-and-conquer.
  • Merge in-place when the inputs share nodes — does it still work? Why?
  • What if the lists are doubly linked? How does the splice change?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why a dummy head?

It removes the special case for the first node. Without it, you need an `if (!result) result = node` branch on every iteration; with it, you always `tail.next = node` and advance.

Is recursion equivalent?

Yes — recursive merge is cleaner but uses O(m+n) stack space. For Vercel's typical bounded inputs it's fine, but the iterative O(1) version is the production-safe choice.

Practice these live with InterviewChamp.AI

Drill Merge Two Sorted Lists and other Vercel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →