Skip to main content

3. Merge Two Sorted Lists

easyAsked at Chegg

Splice two sorted linked lists into one — Chegg uses this to check pointer hygiene on ordered tutor-availability merges.

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

Problem

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. Return the head of the merged linked list.

Constraints

  • 0 <= number of nodes <= 50
  • -100 <= Node.val <= 100
  • Both lists are sorted non-decreasing

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

Pick smaller head, recurse on the rest.

Time
O(n+m)
Space
O(n+m)
function merge(a, b) {
  if (!a || !b) return a || b;
  if (a.val < b.val) { a.next = merge(a.next, b); return a; }
  b.next = merge(a, b.next); return b;
}

Tradeoff:

2. Iterative dummy node

Walk both lists, attach the smaller head to a dummy tail. O(1) extra space beyond the merged list.

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:

Chegg-specific tips

Chegg interviewers prefer the iterative dummy-node solution because it mirrors how their tutor-matching service streams sorted availability windows without per-call allocations.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →