Skip to main content

21. Merge Two Sorted Lists

easyAsked at IBM

Merge Two Sorted Lists is IBM's pointer-discipline check for SWE-1 and intern phone screens. The interviewer is grading whether you reach for a sentinel/dummy node, whether you re-use existing nodes instead of allocating fresh ones, and whether your loop exit cleanly attaches the remaining tail.

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

Source citations

Public interview reports confirming this problem appears in IBM loops.

  • Glassdoor (2026-Q1)— Appears across IBM SWE-1 phone-screen and intern-loop reports.
  • LeetCode (2026-Q1)— Top-frequency IBM-tagged problem.
  • Blind (2025-12)— Listed in IBM new-grad onsite recap thread.

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. Recursive splice

Pick the smaller head, recurse on the rest. Base case: either list is null.

Time
O(n + m)
Space
O(n + m) stack
function mergeTwoListsRecursive(l1, l2) {
  if (l1 === null) return l2;
  if (l2 === null) return l1;
  if (l1.val <= l2.val) {
    l1.next = mergeTwoListsRecursive(l1.next, l2);
    return l1;
  }
  l2.next = mergeTwoListsRecursive(l1, l2.next);
  return l2;
}

Tradeoff: Elegant in 6 lines but O(n+m) call stack — fails on the unbounded follow-up (e.g., 'what if lists are 10^6 long?'). Always mention the stack cost before committing.

2. Iterative with sentinel node (optimal)

Allocate a dummy node, then walk both lists with a tail pointer, attaching the smaller node each step. Attach the remaining list at the end.

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

Tradeoff: Constant extra space and no recursion overhead. The sentinel node eliminates the 'is this the first node we attach?' branch that frequently produces off-by-one bugs.

IBM-specific tips

IBM grades two things on this problem: (1) you reach for a sentinel dummy node unprompted (signals you've internalized the splice pattern), (2) you splice existing nodes instead of allocating new ones (linked-list interview rubric: 'never alloc when you can splice'). Saying 'I'll splice the original nodes' before writing code earns a rubric checkbox on its own.

Common mistakes

  • Allocating new nodes instead of re-using the originals — bloats memory and signals you didn't understand the splice idiom.
  • Forgetting to attach the non-empty remaining list after the loop — the merged list is truncated.
  • Using strict less-than (<) instead of <= in the comparison — fails when both heads are equal.
  • Returning dummy instead of dummy.next — leaks the sentinel into the result.

Follow-up questions

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

  • Merge k Sorted Lists (LeetCode 23) — heap or divide-and-conquer.
  • What if the lists are doubly linked? Does the splice still work?
  • How would you merge if the lists are sorted in opposite orders?
  • Merge two sorted arrays in place (LeetCode 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 use a dummy/sentinel node?

Without it, the first iteration has a special-case 'is the merged list still empty?' check that introduces branch errors. The dummy unifies the loop body so every iteration is identical. Trade 1 byte of stack for cleaner code — every IBM rubric prefers it.

Can I just compare values and copy into a new list?

It works but is the textbook example of allocating when you don't need to. IBM specifically grades 'do you re-use the existing nodes?' on linked-list questions. Allocating fails the senior-bar rubric even if the output is correct.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →