0206.反转链表

https://leetcode.cn/problems/reverse-linked-list/

方法一：链表遍历

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

在遍历解法中, rust Box<ListNode> 由于只用到了所有权的转移，所以实现起来显得较为简洁。

struct Solution;

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}

impl Solution {
    pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut pre = None;
        let mut head = head;
        while let Some(mut p) = head {
            head = p.next;
            p.next = pre;
            pre = Some(p);
        }
        pre
    }
}

方法二：递归链表

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

impl Solution {
    pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        match head {
            None => None,
            Some(mut p) => {
                if p.next.is_none() {
                    return Some(p);
                }
                let next = p.next.take();
                let mut ret = Solution::reverse_list(next);
                let mut q = ret.as_mut().unwrap();
                while q.next.is_some() {
                    q = q.next.as_mut().unwrap();
                }
                q.as_mut().next = Some(p);
                ret
            }
        }
    }
}