Rust每日一题(11)---数据结构-链表--middle-of-the-linked-list

Rust每日一题(11)---数据结构-链表--middle-of-the-linked-list

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

难度: 简单

知识点

思路

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

  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
    }
}
  1. 继续思考如何减小遍历的次数,可以采用一个快指针一次遍历时跳过两个元素,另一个慢指针一次遍历时跳过一个元素,算法复杂度就可以降到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
    }
}

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

  • 发表于 2022-09-02 14:19
  • 阅读 ( 208 )
  • 学分 ( 1 )
  • 分类:Rust

0 条评论

请先 登录 后评论
Johnathan
Johnathan

PhD

24 篇文章, 1335 学分