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

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

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 = []
输出:[]

难度: 简单

知识点

思路

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

  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
}
  1. 原始问题中没有要求初始化链表,如何给链表添加节点同时保存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));
}

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2022-09-02 12:58
  • 阅读 ( 283 )
  • 学分 ( 1 )
  • 分类:Rust

0 条评论

请先 登录 后评论
Johnathan
Johnathan

PhD

24 篇文章, 1335 学分