Rayn Miller
  • 2021年 10月30日
  • 0 阅读

Rust·算法·链表

 

链表 链表的反转 回文判断 中间结点

  • 链表
  • 链表的反转
  • 回文判断
  • 中间结点

链表

  • 重要技巧
    • 使用额外的数据结构记录
      • 栈
      • 哈希表
    • 快慢指针

链表的实现

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 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 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
}
搜索