Merge Two Sorted Lists

1. Define the 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 merged list. Use two pointers , one per list, always taking the smaller front value and advancing that pointer.

Constraints

The number of nodes in both lists is in the range [0, 50]
-100 ≤ Node.val ≤ 100
Both list1 and list2 are sorted in non-decreasing order

Example

Inputlist1 = [1, 2, 4], list2 = [1, 3, 4]

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

Explanation Merging the two sorted lists while always taking the smaller front value produces [1, 1, 2, 3, 4, 4].

2. Know the words first

In plain terms

Linked list: A chain of items where each item points to the next one, like a scavenger hunt where each clue tells you where to find the next.

3. Visualize the solution

Fill the merged list by taking the smaller front value each time

1—

2—

3—

4—

5—

Statusinit

p1=0 (value 1) vs p2=0 (value 1): a tie goes to list1, so 1 fills slot 0.

What happens in this step

p1 = 0 (value 1), p2 = 0 (value 1)
p1.val <= p2.val → 1 <= 1 is true

Tie goes to p1: write 1 into slot 0 of the merged list, then advance p1 to index 1.

Step 1 of 6

Steps to visualize

The row below is the merged list. All six slots are shown from the start; "—" means not filled in yet.
Place a pointer p1 at the head of list1 = [1, 2, 4] and a pointer p2 at the head of list2 = [1, 3, 4].
Compare the values at p1 and p2, writing the smaller one into the next empty slot.
Advance the pointer whose value was just written; the frame marks the slot just filled.
Repeat until one list is exhausted, then append whatever remains of the other list.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Fill the merged list by taking the smaller front value each time

1—

2—

3—

4—

5—

Statusinit

p1=0 (value 1) vs p2=0 (value 1): a tie goes to list1, so 1 fills slot 0.

What happens in this step

p1 = 0 (value 1), p2 = 0 (value 1)
p1.val <= p2.val → 1 <= 1 is true

Tie goes to p1: write 1 into slot 0 of the merged list, then advance p1 to index 1.

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

function mergeTwoLists(values1, values2) {
  function buildList(arr) {
    const dummy = { val: 0, next: null };
    let curr = dummy;
    for (const v of arr) {
      curr.next = { val: v, next: null };
      curr = curr.next;
    }
    return dummy.next;
  }

  let p1 = buildList(values1);
  let p2 = buildList(values2);
  const dummy = { val: 0, next: null };
  let tail = dummy;

  while (p1 && p2) {
    if (p1.val <= p2.val) {
      tail.next = p1;
      p1 = p1.next;
    } else {
      tail.next = p2;
      p2 = p2.next;
    }
    tail = tail.next;
  }

  tail.next = p1 ? p1 : p2;

  const result = [];
  let curr = dummy.next;
  while (curr) {
    result.push(curr.val);
    curr = curr.next;
  }

  return result;
}

Time: O(n + m)
Space: O(n + m)

6. Test cases

Test cases

Input	Expected	Covers
`list1 = [1, 2, 4], list2 = [1, 3, 4]`	`[1, 1, 2, 3, 4, 4]`	example from the docstring
`list1 = [], list2 = [0]`	`[0]`	one list is empty
`list1 = [], list2 = []`	`[]`	both lists are empty
`list1 = [1, 2, 3, 4, 5], list2 = [2]`	`[1, 2, 2, 3, 4, 5]`	lists of very different lengths
`list1 = [1, 2, 3], list2 = [4, 5, 6]`	`[1, 2, 3, 4, 5, 6]`	all values from one list are smaller than the other
`list1 = [5], list2 = [3]`	`[3, 5]`	smallest non-trivial case, one node in each list
`list1 = [1, 1], list2 = [1, 1]`	`[1, 1, 1, 1]`	identical duplicate values across both lists

Merge Two Sorted Lists