- 链表
- 链表的反转
- 回文判断
- 中间结点
链表
- 重要技巧
- 使用额外的数据结构记录
- 栈
- 哈希表
- 快慢指针
- 使用额外的数据结构记录
链表的实现
use std::fmt::Display;
pub struct List {
head: Link,
}
type Link = Option<Box<Node>>;
#[derive(Debug)]
struct Node {
elem: i32,
next: Link,
}
impl Node {
fn new(elem: i32) -> Self {
Self { elem, next: None }
}
}
impl Display for List {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "链表:")?;
if self.head.is_none() {
write!(f, "None")?;
return Ok(());
}
let mut next = self.head.as_ref();
while let Some(node) = next {
write!(f, "{} -> ", node.elem)?;
next = node.next.as_ref();
}
write!(f, "None")?;
Ok(())
}
}
impl List {
fn new() -> Self {
Self { head: None }
}
fn push(&mut self, elem: i32) -> &mut Self {
if self.head.is_none() {
self.head = Some(Box::new(Node::new(elem)));
return self;
}
let mut pnode = self.head.as_mut();
while let Some(cur_node) = pnode {
if cur_node.next.is_none() {
pnode = Some(cur_node);
break;
}
pnode = cur_node.next.as_mut();
}
pnode.map(|node| node.next = Some(Box::new(Node::new(elem))));
self
}
}
链表的反转
fn reverse(&mut self) {
let mut rnode: Link = self.head.take();
let mut lnode: Link = None;
while let Some(mut node) = rnode {
rnode = node.next;
node.next = lnode;
lnode = Some(node);
}
self.head = lnode;
}
fn rev(&mut self) -> &mut Self {
let mut curlink = self.head.take();
let mut prevlink: Option<Box<Node>> = None;
let mut nextlink;
while let Some(mut curnode) = curlink {
nextlink = curnode.next;
curnode.next = prevlink;
prevlink = Some(curnode);
curlink = nextlink;
}
self.head = prevlink;
self
}
找到链表的中间结点
fn middle_node(&self) -> Option<&Box<Node>> {
if self.head.is_none() {
return None;
}
let mut fast = self.head.as_ref();
let mut slow = self.head.as_ref();
while fast.is_some() && fast.unwrap().next.is_some() {
slow = slow.unwrap().next.as_ref();
fast = fast.unwrap().next.as_ref().unwrap().next.as_ref();
}
slow
}
fn middle(&self) -> Option<&Box<Node>> {
if self.head.is_none() {
return None;
}
let mut slow = self.head.as_ref();
let mut fast = self.head.as_ref();
while let Some(fnode) = fast {
fast = fnode.next.as_ref().and_then(|node| node.next.as_ref());
slow = slow.unwrap().next.as_ref();
}
slow
}
判断是否是回文
把链表的数据放到栈中,然后再比对栈中的元素与原链表元素是否相同
或者从链表的中间结点开始,把右侧的元素放入栈中,再与链表左侧元素比较
fn is_palindrome1(&self) -> bool {
if self.head.is_none() {
return true;
}
let mut cur = self.head.as_ref();
let mut v = vec![];
while let Some(node) = cur {
v.push(node.elem);
cur = node.next.as_ref();
}
cur = self.head.as_ref();
for elem in v.into_iter().rev() {
let node = cur.unwrap();
if node.elem != elem {
return false;
}
cur = node.next.as_ref();
}
true
}
找出两个链表相同元素
#![feature(linked_list_cursors)]
use std::cmp::Ordering;
use std::collections::LinkedList;
fn main() {
let list1 = LinkedList::from([1, 2, 3, 4, 5]);
let list2 = LinkedList::from([1, 3, 5]);
let mut list1 = list1.cursor_front();
let mut list2 = list2.cursor_front();
while list1.current().is_some() && list2.current().is_some() {
match list1.current().cmp(&list2.current()) {
Ordering::Greater => list2.move_next(),
Ordering::Less => list1.move_next(),
Ordering::Equal => {
print!("{} ", list2.current().unwrap());
list1.move_next();
list2.move_next();
}
}
}
println!();
}
将单链表划分成左小,中等,右大
单链表放到数组中,再partition
fn partition(nums: &mut [i32], num: i32) -> &mut [i32] {
let mut nlt: usize = 0;
let mut gt: usize = nums.len();
let mut i: usize = 0;
while i < gt {
match nums[i].cmp(&num) {
Ordering::Greater => {
gt -= 1;
nums.swap(i, gt);
}
Ordering::Equal => i += 1,
Ordering::Less => {
nums.swap(i, nlt);
nlt += 1;
i += 1;
}
}
}
nums
}
fn split_list(mut list: List, num: i32) -> List {
let mut curlink = list.head.take();
let mut v: Vec<i32> = vec![];
while let Some(curnode) = curlink {
v.push(curnode.elem);
curlink = curnode.next;
}
partition(&mut v, num);
for elem in v {
list.push(elem);
}
list
}
不用额外数据结构,用有限几个变量
- 可以设置3个变量SH, EH, BH
- 把 < num 的数放到SH链表中
- 把 == num 数放到EH
- 把 > num 放到 BH
- 最后SH->EH->BH
/// 找到链表的最后一个节点
fn list_tail(link: &mut Link) -> &mut Box<Node> {
let mut curlink = link.as_mut();
while let Some(curnode) = curlink {
if curnode.next.is_none() {
curlink = Some(curnode);
break;
}
curlink = curnode.next.as_mut();
}
curlink.unwrap()
}
/// 把节点加到链表的最后
fn append_list(mut curnode: Box<Node>, hd: &mut Link) -> Link {
let next = curnode.next.take();
if hd.is_none() {
*hd = Some(curnode);
} else {
list_tail(hd).next = Some(curnode);
}
next
}
fn split_list2(list: &mut List, num: i32) -> List {
let mut sh: Link = None;
let mut eh: Link = None;
let mut bh: Link = None;
let mut curlink = list.head.take();
while let Some(curnode) = curlink {
let link = match curnode.elem.cmp(&num) {
Ordering::Equal => &mut eh,
Ordering::Greater => &mut bh,
Ordering::Less => &mut sh,
};
curlink = append_list(curnode, link);
}
if sh.is_none() {
sh = eh;
} else {
list_tail(&mut sh).next = eh;
}
list_tail(&mut sh).next = bh;
List { head: sh }
}
fn main() {
let mut list = List::new();
list.from(&random_array(10));
println!("list: {}", list);
let num = random_num(0..5);
println!("num: {}", num);
println!("{}", split_list2(&mut list, num));
}