Skip to main content

3. Merge Two Sorted Lists

easyAsked at Workday

Merge two sorted linked lists into one sorted list. Workday uses this to evaluate pointer hygiene — payroll merges sorted contribution streams (401k, HSA, FSA) into a single time-ordered ledger every cycle.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE1 screen — standard linked-list warmup.
  • LeetCode Discuss (2026)— Workday Pleasanton onsite reported this.

Problem

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists in a 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-and-sort

Walk both lists into an array, sort, rebuild.

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

Tradeoff: Throws away the fact that inputs are sorted. Don't do this.

2. Two-pointer merge with dummy head

Use a dummy node so you never special-case the head. Walk both lists in lockstep.

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: In-place splicing, no new node allocation. The dummy-head pattern is what they grade for.

Workday-specific tips

Workday grades for the dummy-head pattern — without it, you write tedious 'is this the first node?' branches. Also call out that you're SPLICING (rewiring next pointers), not COPYING — important for memory-bounded payroll batch jobs.

Common mistakes

  • Allocating new nodes instead of splicing — wastes memory and earns a stylistic ding.
  • Forgetting to append the remaining tail (l1 || l2) after the loop.
  • Using < instead of <= — breaks stability across equal contribution timestamps.

Follow-up questions

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

  • Merge K Sorted Lists (LC 23) — same pattern, n lists.
  • Sort a linked list (LC 148) — uses merge as the bottom of merge-sort.
  • What if the input lists are unsorted?

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?

Avoids special-casing the head. Without it, you'd need 'if result is null, set head; else, append' on every iteration.

Should this be recursive?

Recursive is elegant but uses O(n+m) stack space. For a 50-node ceiling it's fine; for 50M payroll entries, iterate.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →