leetcode/
reverse_list.rs

1//! # 206. 反转链表
2//!
3//! 难度 简单
4//!
5//! 反转一个单链表。
6//!
7//! ## 示例:
8//!
9//! ```plain
10//! 输入: 1->2->3->4->5->NULL
11//! 输出: 5->4->3->2->1->NULL
12//! ```
13//!
14//! ## 进阶:
15//!
16//! 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
17//!
18//! See [leetcode](https://leetcode-cn.com/problems/reverse-linked-list/)
19//!
20
21use crate::ListNode;
22
23pub struct Solution;
24
25impl Solution {
26    pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
27        Self::iterate(head)
28    }
29
30    #[inline]
31    fn iterate(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
32        head.map(|mut new| {
33            let mut curr = new.next.take();
34            while let Some(mut node) = curr {
35                curr = node.next.replace(new);
36                new = node;
37            }
38            new
39        })
40    }
41
42    #[inline]
43    fn recursion(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
44        head.map(|mut head| {
45            if head.next.is_none() {
46                head
47            } else {
48                Self::recur(head.next.take(), head)
49            }
50        })
51    }
52
53    fn recur(curr: Option<Box<ListNode>>, pre: Box<ListNode>) -> Box<ListNode> {
54        if let Some(mut curr) = curr {
55            Self::recur(curr.next.replace(pre), curr)
56        } else {
57            pre
58        }
59    }
60}
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65    use crate::list;
66
67    #[test]
68    fn test() {
69        let cases = vec![
70            (vec![], list![]),
71            (vec![1,2], list![2,1]),
72            (vec![5,4,3,2,1], list![1,2,3,4,5]),
73        ];
74        let t1 = |v| ListNode::into_vec(Solution::iterate(v));
75        let t2 = |v| ListNode::into_vec(Solution::recursion(v));
76
77        for (expect, head) in cases {
78            assert_eq!(expect, t1(head.clone()));
79            assert_eq!(expect, t2(head));
80        }
81    }
82}
leetcode/reverse_list.rs

leetcode/
reverse_list.rs
