Skip to main content

3. Merge Two Sorted Lists

easyAsked at Datadog

Merge two sorted linked lists into one sorted list. Datadog uses this as a stepping stone toward merging K sorted time-series streams — the underlying two-pointer pattern is identical to how their backend stitches ordered metric shards.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog reports show this as the lead-up to merge-k-sorted-lists.
  • Blind (2025-09)— Recurring Datadog phone screen problem.

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. Collect all + sort

Dump all values into an array, sort, rebuild list.

Time
O((n+m) log(n+m))
Space
O(n+m)
function mergeTwoLists(l1, l2) {
  const vals = [];
  while (l1) { vals.push(l1.val); l1 = l1.next; }
  while (l2) { vals.push(l2.val); l2 = l2.next; }
  vals.sort((a,b) => a - b);
  // rebuild ListNode chain from vals...
}

Tradeoff: Throws away the sorted-input invariant. Don't ship this when the inputs are already ordered.

2. Two-pointer splice (optimal)

Use a dummy head; advance whichever pointer has the smaller value; splice nodes (don't copy).

Time
O(n+m)
Space
O(1)
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(1) extra space, splices nodes in place. Direct analog to merging two ordered metric streams in Datadog's ingestion path.

Datadog-specific tips

Datadog interviewers will follow up with: 'Now do K sorted lists' or 'Now do it lazily — return an iterator that yields one element at a time.' Show that you understand pull-based vs push-based stream merging; mention min-heap for K>2.

Common mistakes

  • Copying node values into new nodes instead of splicing — wastes memory and signals you don't grok linked-list manipulation.
  • Forgetting to attach the leftover tail (l1 || l2) after the loop — drops the tail.
  • Using <= vs < incorrectly — stable merge matters when values tie (preserves origin order).

Follow-up questions

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

  • Merge K Sorted Lists (LC 23) — use a min-heap of head pointers.
  • Sort a linked list using merge sort (LC 148).
  • Merge two sorted arrays in-place when the first has enough trailing space (LC 88).

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 node?

It removes the special case for picking the first node — you don't have to branch on 'which head do I return.' Just return dummy.next at the end.

How does this scale to K lists?

Replace the two-way comparison with a min-heap keyed on node values. Each pop/push is O(log k), giving O(n log k) total.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →