Skip to content
Shubham JangleResources
Linked lists

Explore topics

Merge Sorted LinkedList (Iterative)

Watch the walkthrough
Open on Instagram

Problem

Merge two ascending singly linked lists by relinking their existing nodes. Return the head of the merged list.

Approach and revision checks

The iterative version uses a dummy head and advances the smaller head pointer. O(m+n) time, O(1) auxiliary space. The original file also includes the recursive alternative with the same variable name; running the whole file leaves that last definition active. Run the iterative definition independently for this lesson. Both versions mutate the input links. Supply a ListNode constructor or use the judge's definition.

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;
  }
};