Rust每日一题(10)---数据结构-链表--reverse-linked-list

leetcode地址 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

难度: 简单

知识点

• Option take, as_mut 相关API

思路

核心还是分析关键操作步骤，有两种思路:

1. 采用栈的方式将旧的list的每个数据push到栈中，然后新建一个链表中在将栈中的list全部pop出来并存入到新的链表中，算法复杂度O(2N);
2. 继续思考如何减小更新的次数，考虑到实际上只需要将链表的next值改为之前的值即可。实现上需要用到Option的take API来取到head里面的next值，并进行迭代。

#[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
    }
  }
}

pub fn reverse_list(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut prev = None;
    while let Some(mut temp) = head.take() {
        let next_temp = temp.next.take();
        temp.next = prev; 
        head = next_temp;
        prev = Some(temp);
    }
    prev
}

3. 原始问题中没有要求初始化链表，如何给链表添加节点同时保存head？需要用到Option的as_mut方法，这样可以返回一个可变引用进而对Option内部值进行操作。

//
fn main(){
    let list = vec![1,2,3,4,5];
    let mut head =  Some(Box::new(ListNode::new(list[0])));
    let mut curr = head.as_mut();
    for i in 1..list.len() {
        if let Some(mut node) = curr.take() {
            node.next = Some(Box::new(ListNode::new(list[i])));
            curr = node.next.as_mut();
        }
    }
    println!("{:?}", reverse_list(head));
}