Merge Two Sorted Lists

Try It Yourself

Use the editor below to combine two sorted linked lists. Compare their current nodes and attach the smaller one to the merged tail.

Submit your implementation when it passes the examples. Either list may be empty, and equal or negative values may appear.

Merge Two Sorted Lists

easyLinked List · Two Pointers25 minLC 21

Problem

Given the heads of two sorted singly linked lists, combine their existing nodes into one sorted list.

Return the head of the merged list. Each node has the shape { val, next }.

Example 1:

Input: list1 = [1, 2, 4], list2 = [1, 3, 4]

Output: [1, 1, 2, 3, 4, 4]

Example 2:

Input: list1 = [], list2 = []

Output: []

Constraints

0 ≤ total number of nodes ≤ 100
Both input lists are sorted in non-decreasing order.

0 attempts

Solution

A dummy node gives the merged list a stable starting point. Repeatedly connect the tail to the smaller current node and advance only that list.

When one list ends, connect the remaining part of the other list because it is already sorted.

function mergeTwoLists(list1, list2) {
  const dummy = { val: 0, next: null };
  let tail = dummy;
  let first = list1;
  let second = list2;

  while (first !== null && second !== null) {
    if (first.val <= second.val) {
      tail.next = first;
      first = first.next;
    } else {
      tail.next = second;
      second = second.next;
    }

    tail = tail.next;
  }

  tail.next = first ?? second;
  return dummy.next;
}

Big O notation

Measure	Complexity	Explanation
Time	`O(n + m)`	Every node from both lists is attached once.
Auxiliary space	`O(1)`	Only a dummy node and a fixed number of references are added.