Skip to content
Shubham JangleResources
Linked lists

Explore topics

Merge Sorted LinkedList (Recursive)

Watch the walkthrough
Open on Instagram

Problem

Merge two ascending singly linked lists recursively, returning the smaller head and merging its remainder with the other list.

Approach and revision checks

An empty list is the base case. Each call consumes one node, so time is O(m+n) and worst-case call-stack space is O(m+n). The supplied repository stores both merge versions in file 3; there is no separate file 4. The second definition is the recursive one. Test two empty lists, one empty list, and duplicate values. Very long lists can exceed the JavaScript call-stack limit.

Original repository source

Copied from the supplied local DSA-Series checkout; code and comments are preserved. Run alternative definitions separately when comparing approaches.

3-merge-sorted-linkedlist.js

Original file on GitHub

// Merge the linked lists
// TC: O(M+N), SC: O(1)
var mergeTwoLists = function (list1, list2) {
  const dummy = new ListNode();
  let curr = dummy;

  while (list1 && list2) {
    if (list2.val <= list1.val) {
      curr.next = list2;
      list2 = list2.next;
    } else {
      curr.next = list1;
      list1 = list1.next;
    }
    curr = curr.next;
  }

  curr.next = list1 || list2;

  return dummy.next;
};

// Merge the linked lists - Recursive
// TC: O(M+N), SC: O(M+N) call stack space
var mergeTwoLists = function (list1, list2) {
  if (!list1) return list2;
  if (!list2) return list1;

  if (list1.val < list2.val) {
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  } else {
    list2.next = mergeTwoLists(list1, list2.next);
    return list2;
  }
};