AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【Rust】枚举类型创建单链表以及常见的链表操作方法

2023-07-28 114
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 单链表（Linked List）是一种线性数据结构，由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。单链表的特点是每个节点只能指向一个下一个节点，没有指向上一个节点的指针。

 image.gif


image.gif



单链表

单链表（Linked List）是一种线性数据结构，由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。单链表的特点是每个节点只能指向一个下一个节点，没有指向上一个节点的指针。

单链表的基本操作包括插入、删除、查找等。插入操作需要在指定位置插入一个新节点，删除操作需要删除指定位置的节点，查找操作需要找到指定值的节点位置。

单链表的优势是插入和删除操作相对简单，不需要移动大量元素，时间复杂度为O(1)。但单链表在查找操作上的时间复杂度是O(n)，因为需要从头节点开始逐个比较直到找到目标节点。

image.gif

用枚举表达链表

enum List {
    None,
    Node(i32, Box<List>),
}

image.gif

枚举成员： List::None 、 List::Node(i32, Box)

枚举enum

Rust 是一种编程语言，支持多种类型的的数据，其中之一就是枚举类型（Enum）。枚举类型是一种特殊的数据类型，它定义了一组可能的值。每个值都有一个特定的类型，并且可以用来表示不同的含义。

Rust 中的枚举类型通常使用关键字 enum 来定义，后接名称；枚举有多个成员（variant），每个成员是该 enum 类型的一个可能值。

例如，定义一个表示颜色类型的的枚举：

enum Color { Red, Green, Blue, }

这个 Color 类型有三种可能的值：Red、Green 和 Blue，使用这些值来存储不同颜色的值。

枚举类型的一个重要作用是使得代码更具可读性和可维护性。例如，如果使用一个 String 类型的颜色值，必须要确保该字符串始终有效，否则程序可能会崩溃。而使用枚举类型，可以明确指定可能的值，从而减少了此类错误的发生。

另外，Rust 还支持模式匹配，可以方便地检查一个枚举类型的值是哪个模式，这使得代码更加简洁和可读。例如：

let c = Color::Red;  
match c {  
    Color::Red => println!("It's red!"),  
    Color::Green => println!("It's green!"),  
    Color::Blue => println!("It's blue!"),  
};

image.gif

在这个例子中，使用 match 表达式来检查 c 的值是哪个模式。根据不同的模式，可以执行不同的代码。

Box容器

Rust中的Box是一种通用容器，可以存储任意类型的数据。它类似于C++中的unique_ptr，但还提供了一些额外的功能。

通过使用Box，您可以在堆上分配内存，而不需要手动管理内存的分配和释放。这使得使用Box成为一种方便的方式来存储和管理动态分配的内存。

Box还提供了一些优势，例如能够解决递归类型的大小问题。在Rust中，基本类型无法实现递归，但可以使用Box将递归类型的大小固定下来。

以下是一个使用Box的简单示例：

use std::boxed::Box;  
fn main() {  
    let ibox = Box::new(5);  
    println!("{}", ibox); 
    println!("{}", *ibox);
    println!("{}", ibox.as_ref());
}

image.gif

这个程序创建了一个Box容器，输出结果为3个5，但有不同的含义：

println!("{}", ibox);

这行代码使用 println! 宏打印一个 Box 对象 ibox 的值。{} 是一个占位符，表示将对象的值插入到此处。在这种情况下，ibox 的值将被打印出来，因为 Box 类型实现了 Display trait，可以将其值转换为字符串形式。

println!("{}", *ibox);

这行代码使用 println! 宏打印 ibox 解引用后的值。在 Rust 中，* 运算符用于解引用指针，即获取指针指向的实际值。在这种情况下，ibox 是一个 Box 对象，存储了一个整数值。通过解引用操作，我们获取到这个整数值并打印出来。

println!("{}", ibox.as_ref());

这行代码使用 println! 宏打印 ibox 的引用。as_ref() 方法返回一个引用，可以用于访问 Box 对象中的数据。在这种情况下，我们将 ibox 转换为引用，并通过引用访问其值并打印出来。

通过使用Box，可以方便地在Rust中管理和访问动态分配的内存，而不需要手动管理内存的分配和释放。

创建节点

1. 创建并打印

创建单个节点，并使用 #[derive(Debug)] 及 println! 打印输出：

#[derive(Debug)]
enum List {
    None,
    Node(i32, Box<List>),
}
fn main() {
    let head = List::Node(1, Box::new(List::None));
    println!("{:?}", head);
    let head = List::Node(2, Box::new(List::None));
    println!("{:?}", head);
}

image.gif

输出：

Node(1, None)

Node(2, None)

2. match 匹配

创建节点，并使用match表达式匹配枚举成员：

enum List {
    None,
    Node(i32, Box<List>),
}
fn main() {
    let list1 = List::None;
    let list2 = List::Node(1, Box::new(List::None));
    match list1 {
        List::None => println!("List::None"),
        List::Node(_, _) => println!("List::Node"),
    }
    match list2 {
        List::None => println!("List::None"),
        List::Node(value, _) => println!("List::Node({})", value),
    }
}

image.gif

输出：

List::None

List::Node(1)

3. 节点初始化

new()初始化函数：fn new(value: i32)

#[derive(Debug)]
enum List {
    None,
    Node(i32, Box<List>),
}
impl List {
    fn new(value: i32) -> Self {
        List::Node(value, Box::new(List::None))
    }
}
fn main() {
    let head = List::new(1);
    println!("{:?}", head);
    let head = List::new(2);
    println!("{:?}", head); 
    let head = List::new(3);
    println!("{:?}", head); 
}

image.gif

输出：

Node(1, None)

Node(2, None)

Node(3, None)

4.节点嵌套

通过嵌套多个节点形成单链表：

#[derive(Debug)]
enum List {
    None,
    Node(i32, Box<List>),
}
fn main() {
    let head = List::Node(
        1, Box::new(List::Node(
            2, Box::new(List::Node(
                3, Box::new(List::Node(
                    4, Box::new(List::None),
                )),
            )),
        )),
    );
    println!("{:?}", head);
}

image.gif

输出：

Node(1, Node(2, Node(3, Node(4, None))))

image.gif

通过枚举类型表达成一个单链表，同样，这种方法甚至还能表达一棵二叉树：

#[derive(Debug)]
enum Tree {  
    None,  
    Node(i32, Box<Tree>, Box<Tree>),  
} 
fn main() { 
    let tree = Tree::Node(  
        1,  
        Box::new(Tree::Node(2, Box::new(Tree::None), Box::new(Tree::None))),  
        Box::new(Tree::Node(
            3,
            Box::new(Tree::Node(4, Box::new(Tree::None), Box::new(Tree::None))),
            Box::new(Tree::Node(5, Box::new(Tree::None), Box::new(Tree::None))),
            ),
        ),  
    );   
    println!("{:?}", tree);
}

image.gif

输出：

Node(1, Node(2, None, None), Node(3, Node(4, None, None), Node(5, None, None)))

image.gif

二叉树相对单链表要复杂，有空再研究；还是继续探究单链表的其它操作吧。

追加节点

1. 尾插法

函数 append() 在链表尾部追加节点：

#[derive(Debug)]
enum List {
    None,
    Node(i32, Box<List>),
}
fn append(list: &mut List, value: i32) {
    match list {
        List::None => {
            *list = List::Node(value, Box::new(List::None));
        }
        List::Node(_, next) => {
            append(next, value);
        }
    }
}
fn main() {
    let mut head = List::Node(
        1, Box::new(List::Node(
            2, Box::new(List::Node(
                3, Box::new(List::Node(
                    4, Box::new(List::None),
                )),
            )),
        )),
    );
    println!("{:?}", head);
    append(&mut head, 5);
    println!("{:?}", head);
}

image.gif

输出：

Node(1, Node(2, Node(3, Node(4, None))))

Node(1, Node(2, Node(3, Node(4, Node(5, None)))))

2. 链表追加方法

把append()函数改造成链表方法：

#[derive(Debug)]
enum List {
    None,
    Node(i32, Box<List>),
}
impl List {
    fn new(value: i32) -> Self {
        List::Node(value, Box::new(List::None))
    }
    fn append(self, value: i32) -> Self {
        match self {
            List::None => List::Node(value, Box::new(List::None)),
            List::Node(v, next) => List::Node(v, Box::new(next.append(value))),
        }
    }
}
fn main() {
    let head = List::new(1);
    println!("{:?}", head);
    let head = head.append(2);
    println!("{:?}", head);
    let head = head.append(3);
    println!("{:?}", head);
}

image.gif

输出：

Node(1, None)

Node(1, Node(2, None))

Node(1, Node(2, Node(3, None)))

3. 头插法

除了尾部追加，也能在头部插入： 

#[derive(Debug)]
enum List {
    None,
    Node(i32, Box<List>),
}
fn main() {
    let mut head = List::Node(1, Box::new(List::None));
    head = List::Node(2, Box::new(head));
    head = List::Node(3, Box::new(head));
    head = List::Node(4, Box::new(head));
    println!("{:?}", head);
}

image.gif

输出：

Node(4, Node(3, Node(2, Node(1, None))))

头插法得到一个反序的单链表：

image.gif

4. 改写成单链表方法

对比append()和.push_back()不同之处：

#[derive(Debug)]
enum List {
    None,
    Node(i32, Box<List>),
}
impl List {
    fn new(value: Option<i32>) -> Self {
        match value {
            Some(value) => List::Node(value, Box::new(List::None)),
            None => List::None,
        }
    }
    fn append(self, value: i32) -> Self {
        match self {
            List::None => List::new(Some(value)),
            List::Node(v, next) => List::Node(v, Box::new(next.append(value))),
        }
    }
    fn push_back(&mut self, value: i32) {
        match self {
            List::None => {
                *self = List::new(Some(value));
            }
            List::Node(_, next) => {
                next.push_back(value);
            }
        }
    }
}
fn main() {
    let head = List::new(None);
    println!("{:?}", head);
    let head = head.append(1);
    let head = head.append(2);
    println!("{:?}", head);
    println!();
    let mut head = List::new(Some(1));
    println!("{:?}", head);
    for value in 2..5 {
        head.push_back(value);
    }
    println!("{:?}", head);
}

image.gif

输出：

None

Node(1, Node(2, None))

Node(1, None)

Node(1, Node(2, Node(3, Node(4, None))))

push_back()推荐使用递归法，代码比较精炼；递推迭代法如下：

fn push_back(&mut self, value: i32) {
        match self {
            List::None => {
                *self = List::new(Some(value));
            }
            List::Node(_, next) => {
                if let List::None = &**next {
                    *next = Box::new(List::new(Some(value)));
                } else {
                    let mut curr = next;
                    while let List::Node(_, ref mut next) = **curr {
                        curr = next;
                    }
                    *curr = Box::new(List::new(Some(value)));
                }
            }
        }
    }

image.gif

遍历链表

1. 递归法

#[derive(Debug)]
enum List {
    None,
    Node(i32, Box<List>),
}
fn traverse(list: &List) {
    match list {
        List::None => println!("nil"),
        List::Node(value, next) => {
            print!("{}->", value);
            traverse(next);
        }
    }
}
fn main() {
    let head = List::Node(
        1,
        Box::new(List::Node(
            2,
            Box::new(List::Node(
                3,
                Box::new(List::None),
            )),
        )),
    );
    println!("{:?}", head);
    traverse(&head);
}

image.gif

输出：

Node(1, Node(2, Node(3, None)))

1->2->3->nil

2. 递推法

#[derive(Debug)]
enum List {
    None,
    Node(i32, Box<List>),
}
fn traverse(head: &List) {
    let mut cur = head;
    while let List::Node(value, next) = cur {
        print!("{}->", value);
        cur = next;
    }
    println!("nil");
}
fn main() {
    let head = List::Node(
        1,
        Box::new(List::Node(
            2,
            Box::new(List::Node(
                3,
                Box::new(List::None),
            )),
        )),
    );
    println!("{:?}", head);
    traverse(&head);
}

image.gif

输出：

Node(1, Node(2, Node(3, None)))

1->2->3->nil

while let 语句比较简洁，相当于loop+if let：

fn traverse(head: &List) {
    let mut cur = head;
    loop {
        if let List::Node(value, next) = cur {
            print!("{}->", value);
            cur = next;
        } else {
            println!("nil");
            break;
        }
    }
}

image.gif

使用 loop+match 也能遍历：

fn traverse(head: &List) {
    let mut cur = head;
    loop {
        match cur {
            List::None => {
                println!("nil");
                break;
            }
            List::Node(value, next) => {
                print!("{}->", value);
                cur = next;
            }
        }
    }
}

image.gif

3. 改写成单链表方法 

enum List {
    None,
    Node(i32, Box<List>),
}
impl List {
    fn traverse(&self) {
        let mut curr = self;
        while let List::Node(value, next) = curr {
            print!("{}->", value);
            curr = next;
        }
        println!("nil");
    }
}
fn main() {
    let head = List::Node(
        1, Box::new(List::Node(
            2, Box::new(List::Node(
                3, Box::new(List::None),
            )),
        )),
    );
    head.traverse();
}

image.gif

输出：

1->2->3->nil

自定义Display trait

为与遍历函数区分，在trait输出时用“Nil”标记

use std::fmt;
#[derive(Debug)]
enum List {
    None,
    Node(i32, Box<List>),
}
impl fmt::Display for List {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            List::None => write!(f, "Nil"),
            List::Node(value, next) => {
                write!(f, "{}->", value)?;
                write!(f, "{}", *next)?;
                Ok(())
            }
        }
    }
}
fn traverse(head: &List) {
    let mut cur = head;
    while let List::Node(value, next) = cur {
        print!("{}->", value);
        cur = next;
    }
    println!("nil");
}
fn main() {  
    let head = List::Node(
        1, Box::new(List::Node(
            2, Box::new(List::Node(
                3, Box::new(List::None),
            )),
        )),
    );
    println!("{}", head);
    traverse(&head);
}

image.gif

输出：

1->2->3->Nil

1->2->3->nil

创建链表

直接把动态数组Vec创建成单链表。

1. 递归法

#[derive(Debug)]
enum List {
    None,
    Node(i32, Box<List>),
}
fn traverse(head: &List) {
    let mut cur = head;
    while let List::Node(value, next) = cur {
        print!("{}->", value);
        cur = next;
    }
    println!("nil");
}
fn create(values: Vec<i32>) -> List {
    fn _helper(values: &Vec<i32>, index: usize) -> List {
        if index < values.len() {
            let value = values[index];
            let next = Box::new(_helper(values, index + 1));
            List::Node(value, next)
        } else {
            List::None
        }
    }
    _helper(&values, 0)
}
fn main() {
    let values = vec![1, 2, 3, 4, 5];
    let head = create(values.clone());
    println!("{:?}", head);
    traverse(&head);
}

image.gif

输出：

Node(1, Node(2, Node(3, Node(4, Node(5, None)))))

1->2->3->4->5->nil

2. 递推法

#[derive(Debug)]
enum List {
    None,
    Node(i32, Box<List>),
}
fn traverse(head: &List) {
    let mut cur = head;
    while let List::Node(value, next) = cur {
        print!("{}->", value);
        cur = next;
    }
    println!("nil");
}
fn create(values: Vec<i32>) -> List {
    let mut list = List::None;
    for &value in values.iter().rev() {
        list = List::Node(value, Box::new(list));
    }
    list
}
fn main() {
    let values = vec![1, 2, 3, 4, 5];
    let head = create(values.clone());
    println!("{:?}", head);
    traverse(&head);
}

image.gif

输出：

Node(1, Node(2, Node(3, Node(4, Node(5, None)))))

1->2->3->4->5->nil

3. 改写成单链表方法 

enum List {
    None,
    Node(i32, Box<List>),
}
impl List {
    fn traverse(&self) {
        let mut curr = self;
        while let List::Node(value, next) = curr {
            print!("{}->", value);
            curr = next;
        }
        println!("nil");
    }
    fn create(values: Vec<i32>) -> List {
        let mut list = List::None;
        for &value in values.iter().rev() {
            list = List::Node(value, Box::new(list));
        }
        list
    }
}
fn main() {
    let head = List::create(vec!(1,2,3,4,5));
    head.traverse();
}

image.gif

输出：

1->2->3->4->5->nil

链表长度

遍历链表时改打印为计数即可：

enum List {
    None,
    Node(i32, Box<List>),
}
impl List {
    fn create(values: Vec<i32>) -> List {
        let mut list = List::None;
        for &value in values.iter().rev() {
            list = List::Node(value, Box::new(list));
        }
        list
    }
    fn traverse(&self) {
        let mut curr = self;
        while let List::Node(value, next) = curr {
            print!("{}->", value);
            curr = next;
        }
        println!("nil");
    }
    fn get_size(&self) -> usize {
        let mut length = 0;
        let mut curr = self;
        while let List::Node(_, next) = curr {
            length += 1;
            curr = next;
        }
        length
    }
}
fn main() {
    let head = List::create(vec![1, 2, 3]);
    head.traverse();
    let length = head.get_size();
    println!("Length of list: {}", length);
    let head = List::create(vec![1, 2, 3, 4, 5]);
    head.traverse();
    let length = head.get_size();
    println!("Length of list: {}", length);
}

image.gif

输出：

1->2->3->nil

Length of list: 3

1->2->3->4->5->nil

Length of list: 5

翻转链表

把单链表翻转，即头尾反向。

1. 递归法

#[derive(Debug)]
enum List {
    None,
    Node(i32, Box<List>),
}
fn traverse(head: &List) {
    let mut cur = head;
    while let List::Node(value, next) = cur {
        print!("{}->", value);
        cur = next;
    }
    println!("nil");
}
fn create(values: Vec<i32>) -> List {
    let mut list = List::None;
    for &value in values.iter().rev() {
        list = List::Node(value, Box::new(list));
    }
    list
}
fn reversed(list: &List) -> List {
    fn _helper(list: &List, prev: List) -> List {
        match list {
            List::None => prev,
            List::Node(value, next) => {
                _helper(next, List::Node(*value, Box::new(prev)))
            },
        }
    }
    _helper(list, List::None)
}
fn main() {
    let values = vec![1, 2, 3, 4, 5];
    let head = create(values);
    traverse(&head);
    let head = reversed(&head);
    traverse(&head);
}

image.gif

输出：

1->2->3->4->5->nil

5->4->3->2->1->nil

2. 递推法

enum List {
    None,
    Node(i32, Box<List>),
}
fn traverse(head: &List) {
    let mut curr = head;
    while let List::Node(value, next) = curr {
        print!("{}->", value);
        curr = next;
    }
    println!("nil");
}
fn create(values: Vec<i32>) -> List {
    let mut list = List::None;
    for &value in values.iter().rev() {
        list = List::Node(value, Box::new(list));
    }
    list
}
fn reversed(head: &List) -> List {
    let mut list = List::None;
    let mut curr = head;
    while let List::Node(value, next) = curr {
        list = List::Node(*value, Box::new(list));
        curr = next;
    }
    list
}
fn main() {
    let values = vec![1, 2, 3, 4, 5];
    let head = create(values);
    traverse(&head);
    let head = reversed(&head);
    traverse(&head);
}

image.gif

输出：

1->2->3->4->5->nil

5->4->3->2->1->nil

3. 改写成单链表关联函数和方法

对比关联函数reversed()和方法.reverse()不同之处：

enum List {
    None,
    Node(i32, Box<List>),
}
impl List {
    fn new(value: Option<i32>) -> Self {
        match value {
            Some(value) => List::Node(value, Box::new(List::None)),
            None => List::None,
        }
    }
    fn traverse(&self) {
        let mut curr = self;
        while let List::Node(value, next) = curr {
            print!("{}->", value);
            curr = next;
        }
        println!("nil");
    }
    fn create(values: Vec<i32>) -> List {
        let mut list = List::None;
        for &value in values.iter().rev() {
            list = List::Node(value, Box::new(list));
        }
        list
    }
    fn reversed(&self) -> Self {
        let mut list = List::new(None);
        let mut curr = self;
        while let List::Node(value, next) = curr {
            list = List::Node(*value, Box::new(list));
            curr = next;
        }
        list
    }
    fn reverse(&mut self) {
        let mut tail = List::new(None);
        let mut curr = std::mem::replace(self, List::None);
        while let List::Node(value, next) = std::mem::replace(&mut curr, List::None) {
            let node = List::Node(value, Box::new(tail));
            (tail, curr) = (node, *next);
        }
        std::mem::swap(self, &mut tail);
    }
}
fn main() {
    let values = vec![1, 2, 3, 4, 5];
    let mut head = List::create(values);
    head.traverse();
    head.reverse();
    head.traverse();
    head = List::reversed(&head);
    head.traverse();
}

image.gif

输出：

1->2->3->4->5->nil

5->4->3->2->1->nil

1->2->3->4->5->nil

删除尾节点

删除链表尾节点pop()，并返回尾节点的值

#![allow(dead_code)]
enum List {
    None,
    Node(i32, Box<List>),
}
impl List {
    fn new(value: Option<i32>) -> Self {
        match value {
            Some(value) => List::Node(value, Box::new(List::None)),
            None => List::None,
        }
    }
    fn create(values: Vec<i32>) -> List {
        let mut list = List::None;
        for &value in values.iter().rev() {
            list = List::Node(value, Box::new(list));
        }
        list
    }
    fn traverse(&self) {
        let mut curr = self;
        while let List::Node(value, next) = curr {
            print!("{}->", value);
            curr = next;
        }
        println!("nil");
    }
    fn pop(&mut self) -> Option<i32> {
        match self {
            List::None => None,
            List::Node(value, next) => {
                if let List::None = **next {
                    let popped_value = *value;
                    *self = List::None;
                    Some(popped_value)
                } else {
                    next.pop()
                }
            }
        }
    }
}
fn main() {
    let values = vec![1, 2, 3, 4, 5];
    let mut head = List::create(values);
    head.traverse();
    for _ in 1..=6 {
        if let Some(value) = head.pop() {
            println!("Popped value: {}", value);
        } else {
            println!("List is empty");
        }
        head.traverse();
    }
}

image.gif

输出：

1->2->3->4->5->nil

Popped value: 5

1->2->3->4->nil

Popped value: 4

1->2->3->nil

Popped value: 3

1->2->nil

Popped value: 2

1->nil

Popped value: 1

nil

List is empty

nil

汇总小结

List 枚举定义了链表的两种可能状态：None 和 Node。

其中，Node 表示链表节点，包含一个整数值和一个指向下一个节点的 Box。

相关方法

相关的方法或关联函数，归纳如下：

new：创建一个新的链表节点或空链表。

append：在链表尾部添加一个节点，并返回添加后的链表。

push_back：在链表尾部添加一个节点，将链表修改为添加后的结果。

create：根据给定的数组构建一个链表。

reversed：反转链表，返回一个反转后的链表。

reverse：反转链表，将链表修改为反转后的结果。

traverse：遍历并打印链表中的节点值。

get_size：遍历出链表的节点数，返回链表长度。

pop：删除链表尾节点，并返回尾节点的值。

自定义trait

自定义trait Display，使链表的输出不依赖trait Debug：

```Rust

impl std::fmt::Display for List {

   fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {

       match self {

           List::None => write!(f, "nil"),

           List::Node(value, next) => {

               write!(f, "{}->", value)?;

               write!(f, "{}", *next)?;

               write!(f, "")

           }

       }

   }

}

```

完整代码

InsCode - 让你的灵感立刻落地

https://inscode.csdn.net/@boysoft2002/RustEnumList

#![allow(dead_code)]
enum List {
    None,
    Node(i32, Box<List>),
}
impl std::fmt::Display for List {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        match self {
            List::None => write!(f, "nil"),
            List::Node(value, next) => {
                write!(f, "{}->", value)?;
                write!(f, "{}", *next)?;
                Ok(())
            }
        }
    }
}
impl List {
    fn new(value: Option<i32>) -> Self {
        match value {
            Some(value) => List::Node(value, Box::new(List::None)),
            None => List::None,
        }
    }
    fn append(self, value: i32) -> Self {
        match self {
            List::None => List::new(Some(value)),
            List::Node(v, next) => List::Node(v, Box::new(next.append(value))),
        }
    }
    fn push_back(&mut self, value: i32) {
        match self {
            List::None => {
                *self = List::new(Some(value));
            }
            List::Node(_, next) => {
                next.push_back(value);
            }
        }
    }
    fn create(values: Vec<i32>) -> Self {
        let mut list = List::new(None);
        for &value in values.iter().rev() {
            list = List::Node(value, Box::new(list));
        }
        list
    }
    fn get_size(&self) -> usize {
        let mut length = 0;
        let mut curr = self;
        while let List::Node(_, next) = curr {
            length += 1;
            curr = next;
        }
        length
    }
    fn reversed(&self) -> Self {
        let mut list = List::new(None);
        let mut curr = self;
        while let List::Node(value, next) = curr {
            list = List::Node(*value, Box::new(list));
            curr = next;
        }
        list
    }
    fn reverse(&mut self) {
        let mut tail = List::new(None);
        let mut curr = std::mem::replace(self, List::None);
        while let List::Node(value, next) = std::mem::replace(&mut curr, List::None) {
            let node = List::Node(value, Box::new(tail));
            (tail, curr) = (node, *next);
        }
        std::mem::swap(self, &mut tail);
    }
    fn pop(&mut self) -> Option<i32> {
        match self {
            List::None => None,
            List::Node(value, next) => {
                if let List::None = **next {
                    let popped_value = *value;
                    *self = List::None;
                    Some(popped_value)
                } else {
                    next.pop()
                }
            }
        }
    }
    fn traverse(self: &Self) {
        let mut curr = self;
        while let List::Node(value, next) = curr {
            print!("{}->", value);
            curr = next;
        }
        println!("nil");
    }
}  
fn main() {  
    let head = List::new(None);
    head.traverse();
    let head = head.append(1);
    let head = head.append(2);
    head.traverse();
    println!();
    let mut head = List::new(Some(1));
    head.traverse();
    for value in 2..5 {
        head.push_back(value);
    }
    head.traverse();
    println!();
    let values = vec![1, 2, 3, 4, 5];
    head = List::create(values);
    head.traverse();
    head = head.reversed();
    println!("{}", head);
    head.reverse();
    println!("{}", head);
    let length = head.get_size();
    println!("Length of list: {}", length);
    println!();
    if let Some(value) = head.pop() {
        println!("Popped value: {}", value);
    } else {
        println!("List is empty");
    }
    head.traverse();
    println!("Length of list: {}", head.get_size());
}

image.gif

输出：

nil

1->2->nil

1->nil

1->2->3->4->nil

1->2->3->4->5->nil

5->4->3->2->1->nil

1->2->3->4->5->nil

Length of list: 5

Popped value: 5

1->2->3->4->nil

Length of list: 4

真题实战

合并两个有序链表 Mmerge-two-sorted-lists

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

image.gif


输入：l1 = [1,2,4], l2 = [1,3,4]

输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []

输出：[]

示例 3：

输入：l1 = [], l2 = [0]

输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]

-100 <= Node.val <= 100

l1 和 l2 均按 非递减顺序 排列

代码：

#[derive(Clone)]
enum List {
    None,
    Node(i32, Box<List>),
}
fn create(values: Vec<i32>) -> List {
    let mut list = List::None;
    for &value in values.iter().rev() {
        list = List::Node(value, Box::new(list));
    }
    list
}
fn traverse(head: &List) {
    let mut cur = head;
    while let List::Node(value, next) = cur {
        print!("{}->", value);
        cur = next;
    }
    println!("nil");
}
fn merge_lists(l1: List, l2: List) -> List {
    match (l1.clone(), l2.clone()) {
        (List::None, _) => l2,
        (_, List::None) => l1,
        (List::Node(x, box1), List::Node(y, box2)) => {
            if x < y {
                List::Node(x, Box::new(merge_lists(*box1, l2)))
            } else {
                List::Node(y, Box::new(merge_lists(l1, *box2)))
            }
        }
    }
}
fn main() {
    let nums1 = vec![1, 2, 4];
    let nums2 = vec![1, 2, 3];
    let list1 = create(nums1);
    let list2 = create(nums2);
    traverse(&list1);
    traverse(&list2);
    let merged = merge_lists(list1, list2);
    traverse(&merged);
}

image.gif

输出：

1->2->4->nil

1->2->3->nil

1->1->2->2->3->4->nil

本文完

文章标签：
C++
容器
对象存储
存储
Rust
关键词：
Rust枚举类型
HannYang
目录
相关文章
。思索
|
1月前
|
Rust API
【Rust学习】09_方法语法
结构体让你可以创建出在你的领域中有意义的自定义类型。通过结构体，我们可以将相关联的数据片段联系起来并命名它们，这样可以使得代码更加清晰。在 impl 块中，你可以定义与你的类型相关联的函数，而方法是一种相关联的函数，允许您指定结构体的实例具有的行为。 但是结构体并不是创建自定义类型的唯一方式：让我们转向 Rust 的 enum 功能，将另一个工具添加到你的工具箱中。
。思索
14 0
1483290837038108
|
4月前
|
Rust
rust 引用了Trait的实现，为什么还需要引入Trait 才能调用实现的方法
rust 引用了Trait的实现，为什么还需要引入Trait 才能调用实现的方法
1483290837038108
53 0
好奇的菜鸟
|
5月前
|
Rust 开发者
Rust中的字符串处理及相关方法详解
Rust中的字符串处理及相关方法详解
好奇的菜鸟
67 0
好奇的菜鸟
|
5月前
|
Rust 网络协议
Rust枚举类型详解
Rust枚举类型详解
好奇的菜鸟
25 0
好奇的菜鸟
|
5月前
|
存储 Rust 程序员
Rust结构体详解：定义、使用及方法
Rust结构体详解：定义、使用及方法
好奇的菜鸟
68 0
sumith
|
5月前
数据结构篇：链表和树结构的操作方法
数据结构篇：链表和树结构的操作方法
sumith
49 0
HannYang
|
6月前
|
Rust 索引 Windows
Rust 原始类型之数组array内置方法
Rust 原始类型之数组array内置方法
HannYang
228 0
Rust 原始类型之数组array内置方法
HannYang
|
6月前
|
Java Go C++
Rust每日一练(Leetday0031) 解码方法、复原 IP 地址
Rust每日一练(Leetday0031) 解码方法、复原 IP 地址
HannYang
62 0
Rust每日一练(Leetday0031) 解码方法、复原 IP 地址
HannYang
|
Rust 程序员 索引
Rust 标准库字符串类型String及其46种常用方法
String是一个可变引用，而&str是对该字符串的不可变引用，即可以更改String的数据，但是不能操作&str的数据。String 类型来自标准库，它是可修改、可变长度、可拥有所有权的同样使用UTF-8编码，且它不以空(null)值终止，实际上就是对Vec的包装，在堆内存上分配一个字符串。由&[u8]表示，UTF-8编码的字符串的引用，字符串字面值，也称作字符串切片。
HannYang
439 1
Rust学习日记
|
Rust 编译器 索引
【RUST学习日记】第15课 字符串的常用方法(一)
【RUST学习日记】第15课 字符串的常用方法(一)
Rust学习日记
289 1

热门文章

最新文章

  • 1
    [剑指offer] 复杂链表的复制
  • 2
    《C语言及程序设计》实践参考——改造链表
  • 3
    LeetCode 82 Remove Duplicates from Sorted List II（从已排序链表中移除重复元素）（Linked List）（*）
  • 4
    LeetCode 21：合并两个有序链表 Merge Two Sorted Lists
  • 5
    线性表概述及单链表的Java实现
  • 6
    [LeetCode] Rotate List 旋转链表
  • 7
    从尾到头打印链表
  • 8
    IAM页，IAM链表，分配单元
  • 9
    【转】数据结构链表操作之双链表的基本操作
  • 10
    数据结构之链表（二）
  • 1
    Rust中的生命周期管理：深入理解与实践
    65
  • 2
    使用 Rust 开发一款类似于 GitBook 的程序
    39
  • 3
    Rust 中使用 :: 这种语法的几种情况
    28
  • 4
    rust 引用了Trait的实现，为什么还需要引入Trait 才能调用实现的方法
    53
  • 5
    flutter 调用c++,rust
    41
  • 6
    【unity实战】使用unity制作一个类似Rust的3D生存建造建筑系统，具有很好的吸附性（附项目源码）
    130
  • 7
    使用阿里云镜像加速Rust与Cargo安装及更新
    1067
  • 8
    Rust HashMap详解及单词统计示例
    46
  • 9
    Rust中的字符串处理及相关方法详解
    67
  • 10
    Rust中的Vector：多值存储的利器
    56

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • Go语言核心编程 - 基础语法、数组、切片、Map

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    阿里云OSS设置跨域访问