当Rust遇上LeetCode #206. 反转链表 [简单]

2020/2/7

题目描述

  • 反转一个单链表。

示例

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

相关标签

链表

解题思路

除了记录链表中的每一个值到Vec中,然后重新生成链表的暴.力法以外(O(2n),O(n))。还有两种更快的方法可以采用,分别是迭代法递归法

  • 迭代法
    在遍历链表时,将当前节点的next指针指向前一个元素,第一个节点的next指针需要指向None。另外还需要一个指针来存储下一个节点。
    - 时间复杂度:O(n),假设n为列表的长度,时间复杂度为O(n)。
    - 空间复杂度:O(1)。

  • 递归法
    假设链表m的长度为n,其中[i+1, n]部分的已经被反转,那么m[i]节点的指针应该指向None,m[i+1]节点(若存在)的指针应当指向m[i]。以此类推,最终可以得到一个完整的反转链表。
    - 时间复杂度:O(n),假设n为列表的长度,时间复杂度为O(n)。
    - 空间复杂度:O(n),由于使用递归,将会使用隐式栈空间,递归深度可能达到n层。

源代码

迭代法

// Definition for singly-linked list.
// #[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
//     }
//   }
// }
impl Solution {
    pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        if(head==None){
            return None;
        }
        // 存放当前节点的next指针指向的节点
        let mut node_p1: Option<Box<ListNode>> = None;
        // 存放下一个节点
        let mut node_p2 = &head;
        while let Some(node) = node_p2{
            node_p1 = Some(Box::new(ListNode {
                                        next: node_p1, 
                                        val: node.val}));
            node_p2 = &node.next;
        }
        node_p1
    }
}
  • 执行用时 :0 ms, 在所有 Rust 提交中击败了100.00%的用户
  • 内存消耗 :2.4 MB, 在所有 Rust 提交中击败了44.00%的用户

递归法

use List::*;
// 链表结构
#[derive(Debug)]
enum List { 
    Cons1(i32, Box<List>), 
    Nil,
}
 
// Methods can be attached to an enum
impl List { 
     #[inline]
    fn new() -> List { 
        Nil
    }
    // 在当前节点前新增节点
    #[inline]
    fn prepend(self, elem: i32) -> List { 
        Cons1(elem, Box::new(self))
    }
     // 获取链表长度
    fn len(&self) -> i32 { 
        match *self { 
            Cons1(_, ref tail) => 1 + tail.len(), 
            Nil => 0
        }
    }
     // 将链表转化为字符串
    fn stringify(&self) -> String {
        match 
*self {
            Cons1(head, ref tail) => {
                format!("{}, {}", head, tail.stringify())
            },
            Nil => {
                format!("Nil")
            },
        }
    }
}
 // 反转链表
fn reverse_list(list:List, acc:List ) -> List{
    match list{
        Cons1(val,tail) => {
            reverse_list(*tail,acc.prepend(val))
        }
        Nil => acc
    }
} 
 
fn main() {   
    let mut head = List::new(); 
    let mut i=0; 
    while i < 10 {
        i+=1;
        head = head.prepend(i);
    }
    println!("{:30}",head.stringify());-
    let result = List::new();
    let result = reverse_list(head,result); 
        println!("{}", result.stringify());
}

在不修改原题目函数签名的情况下难以完成, 目前可以通过采用std::List来实现,另外也可以通过unsafe的裸指针来尝试实现,待续。

总结

Rust由于所有权检查的存在,对于链表的操作相较于别的语言会复杂一些。部分情况下可能需要使用unsafe才能完成。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 204,189评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,577评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,857评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,703评论 1 276
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,705评论 5 366
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,620评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,995评论 3 396
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,656评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,898评论 1 298
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,639评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,720评论 1 330
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,395评论 4 319
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,982评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,953评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,195评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 44,907评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,472评论 2 342