Skip to main content

3. Merge Two Sorted Lists

easyAsked at ServiceNow

Splice two sorted linked lists into one sorted list. ServiceNow asks this to test whether you handle dummy-head + tail-pointer mechanics cleanly — the same shape they use when merging two prioritized ticket queues.

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

Source citations

Public interview reports confirming this problem appears in ServiceNow loops.

  • Glassdoor (2026-Q1)— Linked-list merge surfaces in roughly half of ServiceNow new-grad screens.
  • Reddit r/cscareerquestions (2025-12)— Posted as a ServiceNow phone-screen problem with explicit queue-merge framing.

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, sort, rebuild

Walk both lists into an array, sort, build a new linked list.

Time
O((m+n) log(m+n))
Space
O(m+n)
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);
  const dummy = { next: null }; let tail = dummy;
  for (const v of vals) { tail.next = { val: v, next: null }; tail = tail.next; }
  return dummy.next;
}

Tradeoff: Throws away the sortedness invariant. Worse time complexity and allocates new nodes unnecessarily.

2. Dummy head + two-pointer splice

Use a dummy head node. Walk both lists; attach the smaller current node to the tail, advance that list, repeat. Attach the remainder when one list runs out.

Time
O(m + n)
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: Linear time, constant extra space — reuses existing nodes. The dummy head removes the special case for the first node, which is the trick ServiceNow looks for.

ServiceNow-specific tips

ServiceNow uses this to grade pointer hygiene — interviewers watch whether you set up a dummy head to avoid the 'first node is special' branch. Bonus signal: mention this exact pattern is what their priority-queue merge logic uses when an SLA escalation pulls tickets from two different shards.

Common mistakes

  • Forgetting to advance the tail pointer — produces an infinite loop or wrong list.
  • Not attaching the remainder of the non-exhausted list after the while loop.
  • Allocating new nodes instead of splicing existing ones — passes correctness but wastes memory.

Follow-up questions

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

  • Merge k sorted lists (LC 23).
  • Sort a linked list in O(n log n) time (LC 148 — uses this as a subroutine).
  • Merge two sorted lists in place without using a dummy head.

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?

Without it, you have to special-case the first append (head doesn't exist yet vs. head exists). The dummy lets you treat the very first attach the same as every later attach.

Could I do this recursively?

Yes — return l1 with l1.next = merge(l1.next, l2) when l1.val <= l2.val, else symmetric. Same time but O(m+n) recursion-stack space; for the bounded inputs here it's fine, but iterative is more interview-defensible.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →