目录

单链表

用枚举表达链表

枚举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

单链表

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

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

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

用枚举表达链表

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

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

在这个例子中，使用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),}fn main() {let head = List::Node(1, Box::new(List::None));println!("{:" />

输出：

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

2. match 匹配

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

enum List {None,Node(i32, Box),}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),}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),}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, Box),} 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!("{:" />

输出：

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),}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!("{:" />

输出：

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),}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),}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),}impl List {fn new(value: Option) -> 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!("{:" />

输出：

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),}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),}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),}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),}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),}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) -> List {fn _helper(values: &Vec, 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),}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) -> 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),}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) -> 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),}impl List {fn create(values: Vec) -> 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),}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) -> 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),}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) -> 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),}impl List {fn new(value: Option) -> 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) -> 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),}impl List {fn new(value: Option) -> Self {match value {Some(value) => List::Node(value, Box::new(List::None)),None => List::None,}}fn create(values: Vec) -> 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 {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。

相关方法

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

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

输入：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),}fn create(values: Vec) -> 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