206. Reverse Linked List Easy

1/**
2 * [206] Reverse Linked List
3 *
4 * Given the head of a singly linked list, reverse the list, and return the reversed list.
5 *  
6 * Example 1:
7 * <img alt="" src="https://assets.leetcode.com/uploads/2021/02/19/rev1ex1.jpg" style="width: 542px; height: 222px;" />
8 * Input: head = [1,2,3,4,5]
9 * Output: [5,4,3,2,1]
10 * 
11 * Example 2:
12 * <img alt="" src="https://assets.leetcode.com/uploads/2021/02/19/rev1ex2.jpg" style="width: 182px; height: 222px;" />
13 * Input: head = [1,2]
14 * Output: [2,1]
15 * 
16 * Example 3:
17 * 
18 * Input: head = []
19 * Output: []
20 * 
21 *  
22 * Constraints:
23 * 
24 * The number of nodes in the list is the range [0, 5000].
25 * -5000 <= Node.val <= 5000
26 * 
27 *  
28 * Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?
29 * 
30 */
31pub struct Solution {}
32#[allow(unused_imports)]
33use crate::util::linked_list::{ListNode, to_list};
34
35// problem: https://leetcode.com/problems/reverse-linked-list/
36// discuss: https://leetcode.com/problems/reverse-linked-list/discuss/?currentPage=1&orderBy=most_votes&query=
37
38// submission codes start here
39
40// Definition for singly-linked list.
41// #[derive(PartialEq, Eq, Clone, Debug)]
42// pub struct ListNode {
43//   pub val: i32,
44//   pub next: Option<Box<ListNode>>
45// }
46// 
47// impl ListNode {
48//   #[inline]
49//   fn new(val: i32) -> Self {
50//     ListNode {
51//       next: None,
52//       val
53//     }
54//   }
55// }
56impl Solution {
57    pub fn reverse_list(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
58        let mut dummy = Some(Box::new(ListNode{val: 0, next: None}));
59        let rdummy = &mut dummy;
60
61        while let Some(mut n) = head {
62            head = n.next.take();
63            n.as_mut().next = rdummy.as_mut().unwrap().next.take();
64            rdummy.as_mut().unwrap().next = Some(n);
65        }
66        dummy.unwrap().next
67    }
68
69    pub fn reverse_list_reursive(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
70        Self::reverse(None, head)
71    }
72
73    fn reverse(reversed: Option<Box<ListNode>>, head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
74        let mut cur = head;
75        
76        if cur.is_some() {
77            let mut n = cur.take().unwrap();
78            let next = n.next.take();
79            n.next = reversed;
80            Self::reverse(Some(n), next)
81        } else {
82            reversed
83        }
84        
85    }
86}
87
88// submission codes end
89
90#[cfg(test)]
91mod tests {
92    use super::*;
93
94    #[test]
95    fn test_206() {
96        let o = to_list(vec![1,2,3,4,5,6,7]);
97        o.as_ref().unwrap().print();
98        let x = Solution::reverse_list(o);
99        x.as_ref().unwrap().print();
100        let y = Solution::reverse_list_reursive(x);
101        y.as_ref().unwrap().print();
102    }
103}
104