leetcode/
odd_even_linked_list.rs

1//! # 328. 奇偶链表
2//!
3//! 难度 中等
4//!
5//! 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
6//!
7//! 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
8//!
9//! ## 示例 1:
10//!
11//! ```text
12//! 输入: 1->2->3->4->5->NULL
13//! 输出: 1->3->5->2->4->NULL
14//! ```
15//!
16//! ## 示例 2:
17//!
18//! ```text
19//! 输入: 2->1->3->5->6->4->7->NULL
20//! 输出: 2->3->6->7->1->5->4->NULL
21//! ```
22//!
23//! ## 说明:
24//!
25//! - 应当保持奇数节点和偶数节点的相对顺序。
26//! - 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
27//!
28//! See [leetcode](https://leetcode-cn.com/problems/odd-even-linked-list/)
29
30use crate::ListNode;
31
32pub struct Solution;
33
34impl Solution {
35    pub fn odd_even_list(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
36        let mut even_head = None;
37        let mut even_tail = &mut even_head;
38
39        let mut p = &mut head;
40        while let Some(node) = p {
41            if let Some(mut even) = node.next.take() {
42                node.next = even.next.take();
43                *even_tail = Some(even);
44                even_tail = &mut even_tail.as_mut().unwrap().next;
45            }
46
47            if node.next.is_some() {
48                p = &mut node.next;
49            } else {
50                // concat odd tail to even head
51                node.next = even_head;
52                break;
53            }
54        }
55
56        head
57    }
58}
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63    use crate::list;
64
65    #[test]
66    fn test() {
67        let cases = vec![
68            (vec![1,3,5,2,4], list![1,2,3,4,5]),
69            (vec![2,3,6,7,1,5,4], list![2,1,3,5,6,4,7]),
70            (vec![], list![]),
71        ];
72        let t = |v| ListNode::into_vec(Solution::odd_even_list(v));
73        for (expect, input) in cases {
74            assert_eq!(expect, t(input));
75        }
76    }
77}
leetcode/odd_even_linked_list.rs

leetcode/
odd_even_linked_list.rs
