Sort list

Linked List Two Pointers Divide and Conquer Sorting Merge Sort

63.9% acceptance

Jan 12, 2026

12953

414

Given the head of a linked list, return the list after sorting it in ascending order.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn sort_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    if head.is_none() || head.as_ref().unwrap().next.is_none() {
      return head;
    }
    
    // Find the middle and split the list
    let mut len = 0;
    let mut current = &head;
    while let Some(node) = current {
      len += 1;
      current = &node.next;
    }
    
    let mid = len / 2;
    let mut head = head;
    let mut current = &mut head;
    for _ in 0..mid - 1 {
      current = &mut current.as_mut().unwrap().next;
    }
    
    let second = current.as_mut().unwrap().next.take();
    
    // Sort both halves
    let left = Self::sort_list(head);
    let right = Self::sort_list(second);
    
    // Merge
    Self::merge(left, right)
  }
  
  fn merge(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    match (l1, l2) {
      (Some(mut n1), Some(mut n2)) => {
        if n1.val < n2.val {
          n1.next = Self::merge(n1.next, Some(n2));
          Some(n1)
        } else {
          n2.next = Self::merge(Some(n1), n2.next);
          Some(n2)
        }
      }
      (Some(n), None) | (None, Some(n)) => Some(n),
      (None, None) => None,
    }
  }
}