Partition list

Linked List Two Pointers

60.6% acceptance

Jan 12, 2026

7999

983

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn partition_list(head: Option<Box<ListNode>>, x: i32) -> Option<Box<ListNode>> {
    let mut less_head = Box::new(ListNode::new(0));
    let mut greater_head = Box::new(ListNode::new(0));
    let mut less = &mut less_head;
    let mut greater = &mut greater_head;
    let mut current = head;
    
    while let Some(mut node) = current {
      current = node.next.take();
      if node.val < x {
        less.next = Some(node);
        less = less.next.as_mut().unwrap();
      } else {
        greater.next = Some(node);
        greater = greater.next.as_mut().unwrap();
      }
    }
    
    less.next = greater_head.next;
    less_head.next
  }
}