1. Toy模板网首页
  2. > Toy博客

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

9月前 作者：Hann Yang 分类：Toy博客 阅读(40) 违法举报

这篇具有很好参考价值的文章主要介绍了【Rust】枚举类型创建单链表以及常见的链表操作方法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【Rust】枚举类型创建单链表以及常见的链表操作方法,Rust,rust,二叉树,枚举,后端,leetcode

目录

单链表

用枚举表达链表

枚举enum

Box容器

创建节点

1. 创建并打印

2. match 匹配

3. 节点初始化

4.节点嵌套

追加节点

1. 尾插法

2. 链表追加方法

3. 头插法

4. 改写成单链表方法

遍历链表

1. 递归法

2. 递推法

3. 改写成单链表方法 

自定义Display trait

创建链表

1. 递归法

2. 递推法

3. 改写成单链表方法 

链表长度

翻转链表

1. 递归法

2. 递推法

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

删除尾节点

汇总小结

相关方法

自定义trait

完整代码

真题实战

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

【Rust】枚举类型创建单链表以及常见的链表操作方法,Rust,rust,二叉树,枚举,后端,leetcode

单链表

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

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

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

【Rust】枚举类型创建单链表以及常见的链表操作方法,Rust,rust,二叉树,枚举,后端,leetcode

用枚举表达链表

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

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

枚举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!"),  
};

在这个例子中，使用 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());
}

这个程序创建了一个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);
}

输出： 

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),
    }
}

输出：

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); 
}

输出： 

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);
}

输出： 

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

【Rust】枚举类型创建单链表以及常见的链表操作方法,Rust,rust,二叉树,枚举,后端,leetcode

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

#[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);
}

输出： 

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

【Rust】枚举类型创建单链表以及常见的链表操作方法,Rust,rust,二叉树,枚举,后端,leetcode

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

追加节点

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);
}

输出： 

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);
}

输出： 

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);
}

输出： 

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

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

【Rust】枚举类型创建单链表以及常见的链表操作方法,Rust,rust,二叉树,枚举,后端,leetcode

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);
}

输出： 

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)));
                }
            }
        }
    }

遍历链表

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);
}

输出：

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);
}

输出：

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;
        }
    }
}

使用 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;
            }
        }
    }
}

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();
}

输出：

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);
}

输出：

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);
}

输出：

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);
}

输出：

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();
}

输出：

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);
}

输出：

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);
}

输出：

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);
}

输出：

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();
}

输出：

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();
    }
}

输出：

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<List>。

相关方法

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

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());
}

输出：

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：

【Rust】枚举类型创建单链表以及常见的链表操作方法,Rust,rust,二叉树,枚举,后端,leetcode

输入：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);
}

输出：

1->2->4->nil
1->2->3->nil
1->1->2->2->3->4->nil文章来源地址https://www.toymoban.com/news/detail-613917.html

到了这里，关于【Rust】枚举类型创建单链表以及常见的链表操作方法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • rust 初识基础： 变量、数据类型、函数、所有权、枚举

    rust 初识基础： 变量、数据类型、函数、所有权、枚举

    了解到 rust 和 WebAssembly 的结合使用，可以构建前端应用，而且性能也比较好。初步学习使用 rust 是预编译静态类型语言。 官网下载 rust-CN , 大致了解下为什么选择：高性能、可靠性、生产力。 打开控制台啊，执行安装 (mac 系统，windwos 或其他系统查看官网) 安装成功时，会打

    2024年02月07日
    浏览(57)
  • Rust 数据类型 之 类C枚举 c-like enum

    Rust 数据类型 之 类C枚举 c-like enum

    目录 枚举类型 enum 定义和声明 例1：Color 枚举 例2：Direction 枚举 例3：Weekday 枚举 类C枚举 C-like 打印输出 强制转成整数 例1：Weekday 枚举 例2：HttpStatus 枚举 例3：Color 枚举 模式匹配 match 表达式 枚举方法 枚举类型是一种用于表示一组有限数量相互关联的离散型数据，这些值可

    2024年02月16日
    浏览(41)

  • 【PostgreSQL】创建枚举类型和修改枚举值

    1.说明 在postgresql中可以定义枚举数据类型，但是它可以增加和修改枚举值，不能删除已经定义好的枚举值 2.创建枚举类型 创建枚举类型的语法如下，注意枚举类型的顺序就是枚举值的顺序 在表中使用枚举值 3.增加和修改枚举值 如果你想要在已经定义好的枚举类型中添加新的

    2024年01月23日
    浏览(51)

  • 头插法创建单链表、遍历链表、删除链表 | C语言代码

    题目：         输入一系列自然数（0和正整数），输入-1时表示输入结束。按照输入的顺序，用头插法建立单链表，并遍历所建立的单链表，输出这些数据。注意 -1 不加入链表。 输入格式:         第一行是一个正整数k，表示以下会有k组测试数据。         每组

    2024年02月05日
    浏览(38)
  • 链表的总体涵盖以及无哨兵位单链表实现——【数据结构】

    链表的总体涵盖以及无哨兵位单链表实现——【数据结构】

     😊W…Y：个人主页 在学习之前看一下美丽的夕阳，也是很不错的。 如果觉得博主的美景不错，博客也不错的话，关注一下博主吧💕 在上一期中，我们说完了顺序表，并且提出顺序表中的问题 1. 中间/头部的插入删除，时间复杂度为O(N) 2. 增容需要申请新空间，拷贝数据，释

    2024年02月14日
    浏览(68)
  • C语言之单链表的实现以及链表的介绍

    C语言之单链表的实现以及链表的介绍

    因为我们常用的顺序表会存在以下的一些问题： 1. 中间/头部的插入删除，时间复杂度为O(N) 2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。 3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了

    2024年02月01日
    浏览(45)
  • Effective第三版 中英 | 第2章 创建和销毁对象 | 用私有构造器或者枚举类型强化 Singleton 属性

    Effective第三版 中英 | 第2章 创建和销毁对象 | 用私有构造器或者枚举类型强化 Singleton 属性

    大家好，这里是 Rocky 编程日记 ，喜欢后端架构及中间件源码，目前正在阅读 effective-java 书籍。同时也把自己学习该书时的笔记，代码分享出来，供大家学习交流，如若笔记中有不对的地方，那一定是当时我的理解还不够，希望你能及时提出。如果对于该笔记存在很多疑惑，

    2024年02月07日
    浏览(38)
  • 【链表OJ 11】复制带随机指针的链表

    【链表OJ 11】复制带随机指针的链表

    前言:  💥🎈个人主页:​​​​​​Dream_Chaser～ 🎈💥 ✨✨刷题专栏:http://t.csdn.cn/UlvTc ⛳⛳本篇内容:力扣上链表OJ题目 目录 leetcode138. 复制带随机指针的链表 1. 问题描述 2.代码思路: 2.1拷贝节点插入到原节点的后面 2.2控制拷贝节点的random     2.3拷贝节点解下来尾插组成拷

    2024年02月09日
    浏览(51)
  • Java中的链表

    Java中的链表

    上一节中，我们讲过了Java中的ArrayList，当 在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n) ，效率比较低，因此 ArrayList不适合做任意位置插入和删除比较多的场景 。因此：java集合中又引入了LinkedList，即链表结构。 链表是

    2024年02月15日
    浏览(40)
  • 探究Java中的链表

    探究Java中的链表

    引言：         在Java编程中，链表是一种常见的数据结构，具有灵活的内存管理和动态的元素插入与删除能力。本篇博客将深入探讨链表的结构和概念，比较链表与顺序表的区别，介绍Java中LinkedList的常用函数并通过示例说明LinkedList的使用。         链表是一种线性

    2024年01月20日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包