Skip to main content

3. Merge Two Sorted Lists

easyAsked at LINE

Merge two sorted linked lists into one sorted list — LINE uses this as a proxy for merging two ordered chat timelines.

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

Problem

You are given the heads of two sorted linked lists. Splice them together into one sorted linked list by reusing nodes (no new node creation), and return the new head.

Constraints

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

Approaches

1. Collect and sort

Push all values into an array, sort, then rebuild a linked list.

Time
O((m+n) log (m+n))
Space
O(m+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);

Tradeoff:

2. Two pointers with dummy head

Walk both lists with two pointers, attach the smaller node, advance, then append the tail.

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

LINE-specific tips

Frame this as merging two device-side chat-history pages during sync — LINE engineers do exactly this when a phone reconnects after offline.

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

Practice these live with InterviewChamp.AI →