Skip to main content

3. Merge Two Sorted Lists

easyAsked at GitLab

Merge two sorted singly linked lists into one sorted list.

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

Problem

Given the heads of two non-decreasing sorted linked lists list1 and list2, splice them into a single sorted list and return the new head.

Constraints

  • 0 <= n1, n2 <= 50
  • -100 <= node.val <= 100

Examples

Example 1

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

Example 2

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

Approaches

1. Collect and sort

Push all values into array, sort, rebuild.

Time
O((m+n) log(m+n))
Space
O(m+n)
const a=[]; while(l1){a.push(l1.val);l1=l1.next}
while(l2){a.push(l2.val);l2=l2.next}
a.sort((x,y)=>x-y);
// rebuild list

Tradeoff:

2. Two-pointer splice

Walk both with a dummy head, always pick the smaller current.

Time
O(m+n)
Space
O(1)
function merge(l1, l2){
  const dummy={next:null}; let t=dummy;
  while (l1 && l2){
    if (l1.val<=l2.val){ t.next=l1; l1=l1.next; }
    else { t.next=l2; l2=l2.next; }
    t=t.next;
  }
  t.next = l1||l2;
  return dummy.next;
}

Tradeoff:

GitLab-specific tips

GitLab uses linked-list merging as a stand-in for merging commit histories — be ready to discuss conflict resolution when values collide.

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

Practice these live with InterviewChamp.AI →