0
0

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

20210817204340750.png

单链表

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

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

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

用枚举表达链表

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

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

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

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

追加节点

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

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

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：

 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：

d661704fd7a9313cfefde8cc55ef4666.jpg

输入：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

标签： rust 二叉树 枚举
本文转载自: https://blog.csdn.net/boysoft2002/article/details/131930150
版权归原作者 Hann Yang 所有， 如有侵权，请联系我们删除。
登录后发布评论

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

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

机器人技术在安全领域的重要作用

安全学习记录——网络篇（一）

图腾柱PFC：HP1010为您的电动两轮车之旅提供绿色，高效，安全的动力

单元测试数据库回滚问题

这才是单元测试，之前我们都错了

【C语言基础】：字符函数和字符串函数

ChatGPT-Next-Web SSRF漏洞+XSS漏洞复现(CVE-2023-49785)

文章导航