Rust每日一题(11)---数据结构-链表--middle-of-the-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. 遍历链表，并记下总数count,然后从头遍历到count/2的位置，算法复杂度O(1.5N);

impl Solution {
    pub fn middle_node(head: Option<Box<ListNode>>)  -> Option<Box<ListNode>>{
        let mut curr = head.as_ref();
        let mut count = 0;
        while let Some(mut temp) = curr.take() {
            curr = temp.next.as_ref();
            count += 1;
        }
        count = count /2 ;
        let mut res = head;
        while count > 0 {
            res = res.and_then(|x|{x.next});
            count -= 1;
        }
        res
    }
}

2. 继续思考如何减小遍历的次数，可以采用一个快指针一次遍历时跳过两个元素，另一个慢指针一次遍历时跳过一个元素，算法复杂度就可以降到O(N)。

impl Solution {
    pub fn middle_node(head: Option<Box<ListNode>>)  -> Option<Box<ListNode>>{
        let mut curr = head.as_ref();
        let mut res = head.clone();
        while curr.is_some() && curr.unwrap().next.is_some() {
            curr = curr.unwrap().next.as_ref().unwrap().next.as_ref();
            res = res.take().and_then(|x|{x.next});
        }
        res
    }
}