Skip to main content

3. Merge Two Sorted Lists

easyAsked at Udemy

Merge two sorted linked lists into one sorted list — Udemy uses this to test pointer hygiene before deeper recommendation-feed merge questions.

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

Problem

You are given the heads of two sorted linked lists list1 and list2. Splice their nodes together into one sorted list and return its head.

Constraints

  • 0 <= total nodes <= 50
  • -100 <= Node.val <= 100
  • Both lists 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=[0]
Output
[0]

Approaches

1. Collect and sort

Dump values into an array, sort, then rebuild a list.

Time
O(n log n)
Space
O(n)
const vals = [];
for (const head of [l1, l2]) for (let n = head; n; n = n.next) vals.push(n.val);
vals.sort((a,b)=>a-b);
const dummy = { val: 0, next: null }; let cur = dummy;
for (const v of vals) { cur.next = { val: v, next: null }; cur = cur.next; }
return dummy.next;

Tradeoff:

2. Two pointers in place

Walk both lists with a dummy head, attaching the smaller node each step. Append any leftover tail.

Time
O(n+m)
Space
O(1)
function merge(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:

Udemy-specific tips

Udemy interviewers like to extend this to merging two ranked course recommendation streams — be ready to discuss tie-breakers when scores are equal.

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 Udemy interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →