{"content":{"title":"Rust每日一题(11)---数据结构-链表--middle-of-the-linked-list","body":"# Rust每日一题(11)---数据结构-链表--middle-of-the-linked-list\r\n[leetcode地址](https:\/\/leetcode.cn\/problems\/middle-of-the-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. 遍历链表，并记下总数count,然后从头遍历到count\/2的位置，算法复杂度O(1.5N);\r\n\r\n```\r\nimpl Solution {\r\n    pub fn middle_node(head: Option<Box<ListNode>>)  -> Option<Box<ListNode>>{\r\n        let mut curr = head.as_ref();\r\n        let mut count = 0;\r\n        while let Some(mut temp) = curr.take() {\r\n            curr = temp.next.as_ref();\r\n            count += 1;\r\n        }\r\n        count = count \/2 ;\r\n        let mut res = head;\r\n        while count > 0 {\r\n            res = res.and_then(|x|{x.next});\r\n            count -= 1;\r\n        }\r\n        res\r\n    }\r\n}\r\n```\r\n\r\n2. 继续思考如何减小遍历的次数，可以采用一个快指针一次遍历时跳过两个元素，另一个慢指针一次遍历时跳过一个元素，算法复杂度就可以降到O(N)。\r\n\r\n```\r\nimpl Solution {\r\n    pub fn middle_node(head: Option<Box<ListNode>>)  -> Option<Box<ListNode>>{\r\n        let mut curr = head.as_ref();\r\n        let mut res = head.clone();\r\n        while curr.is_some() && curr.unwrap().next.is_some() {\r\n            curr = curr.unwrap().next.as_ref().unwrap().next.as_ref();\r\n            res = res.take().and_then(|x|{x.next});\r\n        }\r\n        res\r\n    }\r\n}\r\n```"},"author":{"user":"https:\/\/learnblockchain.cn\/people\/720","address":null},"history":null,"timestamp":1662099591,"version":1}