Skip to main content

3. Merge Two Sorted Lists

easyAsked at GoDaddy

Combine two sorted linked lists into one sorted list by splicing nodes.

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

Problem

Merge two sorted linked lists and return the head of the merged sorted list. The list should be made by splicing together the nodes of the first two lists.

Constraints

  • 0 <= list nodes <= 50
  • Node values in [-100, 100]
  • Both lists sorted non-decreasing

Examples

Example 1

Input
l1 = [1,2,4], l2 = [1,3,4]
Output
[1,1,2,3,4,4]

Example 2

Input
l1 = [], l2 = []
Output
[]

Approaches

1. Collect and sort

Push all values into an array, sort, rebuild list.

Time
O(n log n)
Space
O(n)
const arr=[]; while(l1){arr.push(l1.val);l1=l1.next;} while(l2){arr.push(l2.val);l2=l2.next;} arr.sort((a,b)=>a-b); /* rebuild */

Tradeoff:

2. Dummy head two pointer merge

Walk both lists; attach the smaller node to a dummy tail.

Time
O(n+m)
Space
O(1)
function mergeTwoLists(l1, l2) {
  const dummy = { 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:

GoDaddy-specific tips

At GoDaddy this mirrors merging two sorted streams of DNS records from primary and secondary nameservers during a zone transfer.

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

Practice these live with InterviewChamp.AI →