Merge two sorted lists

Linked List Recursion

68.0% acceptance

Jan 12, 2026

24783

2426

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn merge_two_lists(list1: Option<Box<ListNode>>, list2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    match (list1, list2) {
      (None, None) => None,
      (Some(node), None) | (None, Some(node)) => Some(node),
      (Some(mut l1), Some(mut l2)) => {
        if l1.val <= l2.val {
          l1.next = Solution::merge_two_lists(l1.next, Some(l2));
          Some(l1)
        } else {
          l2.next = Solution::merge_two_lists(Some(l1), l2.next);
          Some(l2)
        }
      }
    }
  }
}