Stage 1: Foundations·Linked Lists

Easy#216 min readLinked ListsTwo PointersLeetCode

Merge Two Sorted Lists

Dummy head merge

Merge step of merge sort. In Rust, practice with Option<Box<ListNode>>.

Published Apr 15, 2026

Problem

You are given the heads of two sorted linked lists, list1 and list2.

Merge the lists into one sorted list by splicing together their nodes, and return the head of the merged list.

Input

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

Output

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

Input

list1 = [], list2 = []

Output

[]

Intuition

This is the merge step of merge sort, stripped down to its smallest useful form.

At every step, the only question is: which current head is smaller? Take that node, advance that list, and append the chosen node to the tail of the output. Because both input lists are already sorted, the global order stays sorted if each local choice is correct.

The dummy head removes the only annoying part of linked-list construction: the first node. After that, every append is the same operation.

Approach

Dummy Head Merge

TimeO(m + n)

SpaceO(1)

Recommended

Keep a tail pointer to the end of the merged list. Compare the current heads, splice the smaller one onto tail.next, and advance that input list. When one list runs out, attach the rest of the other list in one shot.

impl Solution {
    pub fn merge_two_lists(
        mut list1: Option<Box<ListNode>>,
        mut list2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        let mut dummy = Box::new(ListNode { val: 0, next: None });
        let mut tail = &mut dummy;

        while list1.is_some() && list2.is_some() {
            let take_left = list1.as_ref().unwrap().val <= list2.as_ref().unwrap().val;
            let mut node= if take_left {
                let mut node= list1.take().unwrap();
                list1= node.next.take();
                node
            } else {
                let mut node= list2.take().unwrap();
                list2= node.next.take();
                node
            };

            tail.next= Some(node);
            tail= tail.next.as_mut().unwrap();
        }

        tail.next= if list1.is_some() { list1 } else { list2 };
        dummy.next
    }
}

Rust · runnable

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);
  let tail = dummy;

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

  tail.next = list1 ?? list2;
  return dummy.next;
}

TypeScript · runnable

Recursive Merge

TimeO(m + n)

SpaceO(m + n)

The recursive version is the same decision rule written as a structural recursion: the smaller head becomes the new head, and its next pointer is filled by merging the rest.

It is concise and easy to prove correct. It is also linear stack depth, so the iterative version is the one to prefer when input size is not tiny.

impl Solution {
    pub fn merge_two_lists(
        list1: Option<Box<ListNode>>,
        list2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        match (list1, list2) {
            (None, x) | (x, None) => x,
            (Some(mut a), Some(mut b)) => {
                if a.val <= b.val {
                    let next= a.next.take();
                    a.next= Self::merge_two_lists(next, Some(b));
                    Some(a)
                } else {
                    let next= b.next.take();
                    b.next= Self::merge_two_lists(Some(a), next);
                    Some(b)
                }
            }
        }
    }
}

Rust · runnable

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  if (list1 === null) return list2;
  if (list2 === null) return list1;

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

  list2.next = mergeTwoLists(list1, list2.next);
  return list2;
}

TypeScript · runnable

Trace

Merging list1 = [1,2,4] and list2 = [1,3,4]:

step	chosen node	list1 head	list2 head	merged prefix
start	—	1	1	[]
1	1 from list1	2	1	[1]
2	1 from list2	2	3	[1,1]
3	2 from list1	4	3	[1,1,2]
4	3 from list2	4	4	[1,1,2,3]
5	4 from list1	null	4	[1,1,2,3,4]
6	4 from list2	null	null	[1,1,2,3,4,4]

Once one list is exhausted, the rest of the other list can be attached without further comparisons.

Edge cases

One list empty — return the other list unchanged.
Equal values — either side is valid, but taking from list1 first preserves stability.
One list much longer — the tail append handles the remainder in O(1).

Takeaway

Merging sorted lists is the base case for more complicated linked-list composition. Once this feels trivial, merge k sorted lists, reorder list, and even many tree/array merge problems become the same exercise at a larger scale.

Easy#206

Reverse Linked List

Three pointers: prev, curr, next. Draw it out. Do both iterative and recursive.

Medium#143

Reorder List

Combines three techniques: find middle, reverse second half, merge.

Hard#23

Merge k Sorted Lists