#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)
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
}
}