leetcode/util/
linked_list.rs

1
2/// LeetCode 里常用到的链表节点结构
3// Definition for singly-linked list.
4#[derive(PartialEq, Eq, Clone, Debug)]
5pub struct ListNode {
6  pub val: i32,
7  pub next: Option<Box<ListNode>>,
8}
9
10impl ListNode {
11  #[inline]
12    pub fn new(val: i32) -> Self {
13        ListNode {
14            next: None,
15            val
16        }
17    }
18
19    /// 从 `Vec<i32>` 构建链表结构。建议使用宏 [`list!`](list)
20    pub fn from_vec(vec: Vec<i32>) -> Option<Box<ListNode>> {
21        vec_to_list(vec)
22    }
23
24    pub fn into_vec(list: Option<Box<ListNode>>) -> Vec<i32> {
25        let mut rest = list;
26        std::iter::from_fn(move || {
27            if let Some(node) = rest.as_mut() {
28                let val = Some(node.val);
29                rest = node.next.take();
30                val
31            } else {
32                None
33            }
34        }).collect()
35    }
36}
37
38pub fn vec_to_list(vec: Vec<i32>) -> Option<Box<ListNode>> {
39    vec.into_iter().rev().fold(None, |next, val| {
40        Box::new(ListNode {
41            val,
42            next,
43        }).into()
44    })
45}
46
47/// Generate a linked list from a vec-like syntax.
48///
49/// For example:
50///
51/// ```no_run
52/// #[macro_use] extern crate leetcode;
53/// use leetcode::ListNode;
54/// let head: Option<Box<ListNode>> = list![1,2,3,4];
55/// // head:
56/// // 1 -> 2 -> 3 -> 4 -> None
57///
58/// let head = list![1i32; 5];
59/// // head:
60/// // 1 -> 1 -> 1 -> 1 -> 1 -> None
61/// ```
62#[macro_export]
63macro_rules! list {
64    () => {
65        None
66    };
67    ($elem:expr; $n:expr) => {
68        $crate::ListNode::from_vec(vec![$elem; $n])
69    };
70    ($($x:expr),+ $(,)?) => {
71        $crate::ListNode::from_vec(vec![$($x),+])
72    };
73}
74
75#[cfg(test)]
76mod tests {
77    use super::*;
78
79    #[test]
80    fn test() {
81        let f = |v| ListNode::from_vec(v);
82        let into = |v| ListNode::into_vec(v);
83        assert_eq!(vec![0i32;0], into(f(vec![])));
84        assert_eq!(vec![1,2,3], into(f(vec![1,2,3])));
85    }
86
87    #[test]
88    fn test_list_macro() {
89        let l1 = list![1,2,3,4];
90        assert_eq!(vec![1,2,3,4], ListNode::into_vec(l1));
91        assert_eq!(None::<Option<Box<ListNode>>>, list![]);
92        assert_eq!(vec![1,1,1,1,1], ListNode::into_vec(list![1i32;5]));
93        assert_eq!(vec![1], ListNode::into_vec(list![1]));
94    }
95}
leetcode/util/linked_list.rs

leetcode/util/
linked_list.rs
