Skip to main content

3. Merge Two Sorted Lists

easyAsked at Palantir

Merge two sorted linked lists into one sorted list. Palantir asks this to gauge pointer hygiene since their ETL transforms frequently merge sorted streams of records by primary key.

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

Source citations

Public interview reports confirming this problem appears in Palantir loops.

  • Glassdoor (2025-12)— Palantir FDE phone screen, paired with merge-k-sorted-lists follow-up.
  • Blind (2025-08)— Cited as warm-up before merge-sort-on-disk pipeline question.

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
[]

Example 3

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

Approaches

1. Collect to array then sort

Push all values to an array, sort, rebuild list.

Time
O((n+m) log(n+m))
Space
O(n+m)
function merge(a, b) {
  const arr = [];
  while (a) { arr.push(a.val); a = a.next; }
  while (b) { arr.push(b.val); b = b.next; }
  arr.sort((x,y) => x-y);
  // rebuild list...
}

Tradeoff: Ignores the sorted invariant. Palantir interviewers will mark this as the anti-pattern.

2. Two-pointer splice with dummy head

Walk both lists with two pointers; append the smaller node to a tail and advance. Use a dummy head to simplify edge cases.

Time
O(n+m)
Space
O(1)
function mergeTwoLists(a, b) {
  const dummy = { next: null };
  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;
}

Tradeoff: Linear time, O(1) extra space. The dummy head is the canonical trick for any 'build a list' problem.

Palantir-specific tips

Palantir grades this on the dummy-head trick and on splicing existing nodes instead of allocating new ones. Mention that this is the inner loop of a merge-sort on a sorted ETL stream — if you allocate per record, your pipeline OOMs on a 1TB dataset. Use <= (not <) so the merge is stable on equal keys, since stability matters for joins.

Common mistakes

  • Allocating a new node for every merged value instead of splicing existing ones — doubles memory.
  • Using < instead of <= — breaks stability, which downstream joins assume.
  • Forgetting to attach the remaining tail (a || b) after one list is exhausted.

Follow-up questions

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

  • Merge k sorted lists (LC 23) — solve with a min-heap.
  • What if the lists are too large to fit in memory and live on disk? (External merge sort.)
  • Merge two sorted streams where each emits (key, value) — and de-duplicate by key.

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 use a dummy head?

It eliminates the special case for the first node. Without it, you'd have a separate if-branch for 'is this the first iteration?' on every loop. The dummy node is allocated once and discarded at return.

Why is stability important here?

If two records have the same join key, downstream code often assumes the one from list1 comes first. An unstable merge can swap them and cause subtle bugs in joins.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →