{"content":{"title":"Rust每日一题(10)---数据结构-链表--reverse-linked-list","body":"# Rust每日一题(10)---数据结构-链表--reverse-linked-list\r\n[leetcode地址](https:\/\/leetcode.cn\/problems\/reverse-linked-list\/)\r\n给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。\r\n\r\n**示例 1：**\r\n```\r\n输入：head = [1,2,3,4,5]\r\n输出：[5,4,3,2,1]\r\n```\r\n**示例 2：**\r\n```\r\n输入：head = [1,2]\r\n输出：[2,1]\r\n```\r\n\r\n**示例 3：**\r\n```\r\n输入：head = []\r\n输出：[]\r\n```\r\n\r\n**难度: 简单**\r\n\r\n## 知识点\r\n- Option [ take, as_mut 相关API](https:\/\/doc.rust-lang.org\/std\/option\/enum.Option.html#method.take)\r\n\r\n## 思路\r\n核心还是分析关键操作步骤，有两种思路:\r\n\r\n1. 采用栈的方式将旧的list的每个数据push到栈中，然后新建一个链表中在将栈中的list全部pop出来并存入到新的链表中，算法复杂度O(2N);\r\n2. 继续思考如何减小更新的次数，考虑到实际上只需要将链表的next值改为之前的值即可。实现上需要用到Option的take API来取到head里面的next值，并进行迭代。\r\n\r\n```\r\n#[derive(PartialEq, Eq, Clone, Debug)]\r\npub struct ListNode {\r\n  pub val: i32,\r\n  pub next: Option<Box<ListNode>>\r\n}\r\n\r\nimpl ListNode {\r\n  #[inline]\r\n  fn new(val: i32) -> Self {\r\n    ListNode {\r\n      next: None,\r\n      val\r\n    }\r\n  }\r\n}\r\n\r\npub fn reverse_list(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {\r\n    let mut prev = None;\r\n    while let Some(mut temp) = head.take() {\r\n        let next_temp = temp.next.take();\r\n        temp.next = prev; \r\n        head = next_temp;\r\n        prev = Some(temp);\r\n    }\r\n    prev\r\n}\r\n\r\n```\r\n\r\n3. 原始问题中没有要求初始化链表，如何给链表添加节点同时保存head？需要用到Option的as_mut方法，这样可以返回一个可变引用进而对Option内部值进行操作。\r\n\r\n```\r\n\/\/\r\nfn main(){\r\n    let list = vec![1,2,3,4,5];\r\n    let mut head =  Some(Box::new(ListNode::new(list[0])));\r\n    let mut curr = head.as_mut();\r\n    for i in 1..list.len() {\r\n        if let Some(mut node) = curr.take() {\r\n            node.next = Some(Box::new(ListNode::new(list[i])));\r\n            curr = node.next.as_mut();\r\n        }\r\n    }\r\n    println!(\"{:?}\", reverse_list(head));\r\n}\r\n```"},"author":{"user":"https:\/\/learnblockchain.cn\/people\/720","address":null},"history":null,"timestamp":1662094728,"version":1}