Reorder list

Linked List Two Pointers Stack Recursion

64.6% acceptance

Jan 12, 2026

12454

513

You are given the head of a singly linked-list. The list can be represented as: L0 → L1 → … → Ln - 1 → Ln Reorder the list to be on the following form: L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn reorder_list(head: &mut Option<Box<ListNode>>) {
    if head.is_none() || head.as_ref().unwrap().next.is_none() {
      return;
    }
    
    // Find the middle of the list
    let mut len = 0;
    let mut current = head.as_ref();
    while let Some(node) = current {
      len += 1;
      current = node.next.as_ref();
    }
    
    let mid = (len + 1) / 2;
    
    // Split the list at the middle
    let mut current = head.as_mut();
    for _ in 0..mid - 1 {
      current = current.unwrap().next.as_mut();
    }
    
    let mut second_half = current.unwrap().next.take();
    
    // Reverse the second half
    let mut prev: Option<Box<ListNode>> = None;
    while let Some(mut node) = second_half {
      second_half = node.next.take();
      node.next = prev;
      prev = Some(node);
    }
    
    // Merge the two halves
    let mut first = head.take();
    let mut second = prev;
    let mut dummy = Box::new(ListNode::new(0));
    let mut tail = &mut dummy;
    
    while first.is_some() || second.is_some() {
      if let Some(mut node) = first {
        first = node.next.take();
        tail.next = Some(node);
        tail = tail.next.as_mut().unwrap();
      }
      if let Some(mut node) = second {
        second = node.next.take();
        tail.next = Some(node);
        tail = tail.next.as_mut().unwrap();
      }
    }
    
    *head = dummy.next;
  }
}