Skip to main content

3. Merge Two Sorted Lists

easyAsked at Gojek

Merge two sorted linked lists into one sorted list by splicing nodes together.

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

Problem

You are given the heads of two sorted linked lists list1 and list2. Merge them into one sorted list by splicing together the nodes of the first two lists. Return the head of the merged linked list.

Constraints

  • 0 <= total nodes <= 50
  • -100 <= Node.val <= 100
  • Both lists are sorted ascending

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. Convert to array and sort

Drain both into an array, sort, rebuild list.

Time
O(n log n)
Space
O(n)
const arr = [];
let n = list1; while(n){arr.push(n.val); n=n.next;}
n = list2; while(n){arr.push(n.val); n=n.next;}
arr.sort((a,b)=>a-b);

Tradeoff:

2. Dummy head two-pointer merge

Walk both lists, attaching the smaller node each step. Append remainder at end.

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:

Gojek-specific tips

Gojek favors candidates who write clean pointer-manipulation code without auxiliary arrays since their driver-event streams must be merged in-place to control GC pressure.

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

Practice these live with InterviewChamp.AI →