Skip to main content

3. Merge Two Sorted Lists

easyAsked at Byju's

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

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

Problem

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

Constraints

  • 0 <= 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 = [0]
Output
[0]

Approaches

1. Copy to array

Dump all values into an array, sort, rebuild a 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 list from arr

Tradeoff:

2. Dummy-head splice

Walk both lists with a dummy head and append the smaller node. Linear merge ignores already-sorted ordering.

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:

Byju's-specific tips

Byju's panels reward candidates who draw the linked list and step through nodes verbally as if teaching a school class.

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

Practice these live with InterviewChamp.AI →