[Rust] Itertaive, in-place re-ordering with O(1) additional space
\nrust\nuse std::hint::unreachable_unchecked;\n\npub fn reorder_list(head: &mut Option<Box<ListNode>>) {\n    // Find how many nodes are in the list;\n    let m
\n```rust\nuse std::hint::unreachable_unchecked;\n\npub fn reorder_list(head: &mut Option<Box<ListNode>>) {\n    // Find how many nodes are in the list;\n    let mut count = 0;\n    let mut list = &*head;\n\n    while let Some(node) = list {\n        list = &node.next;\n        count += 1;\n    }\n\n    // If there are less than two nodes, then there is nothing to do\n    if count <= 2 {\n        return;\n    }\n\n    // Reach the middle of the list in order to split in to two lists\n    let mut half = head.as_mut();\n    for _ in 0..count / 2 {\n        match half {\n            // SAFETY: we have counted the number of nodes, so we know there are more nodes\n            None => unsafe { unreachable_unchecked() },\n            Some(node) => {\n                half = node.next.as_mut();\n            }\n        }\n    }\n\n    // Reverse the second half\n    let mut half = match half {\n        // SAFETY: we have counted the number of nodes, so we know there are more nodes\n        None => unsafe { unreachable_unchecked() },\n        Some(node) => node.next.take(),\n    };\n\n    let mut reversed = ListNode::new(0);\n    while let Some(mut node) = half.take() {\n        half = node.next.take();\n        node.next = reversed.next.take();\n        reversed.next = Some(node);\n    }\n\n    // merge the two lists, tail points to the node in the first list\n    // that has to be disconnected in order to put a node from the reversed\n    // list in its place. Then it\'s reattached as "next" of the new node\n    let mut tail = match head.as_mut() {\n        // SAFETY: we know there is node at HEAD\n        None => unsafe { unreachable_unchecked() },\n        Some(node) => &mut node.next,\n    };\n\n    while tail.is_some() && reversed.next.is_some() {\n        // SAFETY: We know there is a reversed.next because we already checked it\n        let mut rev = reversed.next.take().unwrap();\n        reversed.next = rev.next.take();\n\n        rev.next = tail.take();\n        *tail = Some(rev);\n        tail = &mut tail.as_mut().unwrap().next;\n        if let Some(node) = tail {\n            tail = &mut node.next;\n        }\n    }\n}\n```
['Rust']