Skip to main content
Back to problems
#2046
Medium Algorithms

Sort linked list already sorted using absolute values

Linked List Two Pointers Sorting
67.1% acceptance
Mar 31, 2026
175
3

No description available.

Solution

Rust
Time O(n)
Space O(1)
LeetCode
solution.rs
impl Solution {
  pub fn sort_linked_list(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut neg_head: Option<Box<ListNode>> = None;
    let mut pos_dummy = Box::new(ListNode::new(0));
    let mut pos_tail = &mut pos_dummy;

    while let Some(mut node) = head {
      head = node.next.take();
      if node.val < 0 {
        node.next = neg_head;
        neg_head = Some(node);
      } else {
        pos_tail.next = Some(node);
        pos_tail = pos_tail.next.as_mut().unwrap();
      }
    }

    if neg_head.is_none() {
      return pos_dummy.next;
    }

    let mut neg_tail = &mut neg_head;
    while neg_tail.as_ref().unwrap().next.is_some() {
      neg_tail = &mut neg_tail.as_mut().unwrap().next;
    }
    neg_tail.as_mut().unwrap().next = pos_dummy.next;

    neg_head
  }
}