2022-08-18

通过算法学习rust之反转链表

题目地址

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    }
}

知识点列举

take()方法
mem::replace()方法

解题思路

impl Solution {
    pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut res: Option<Box<ListNode>> = None;
        let mut current = head;
        // 保存当前节点为tmp
        while let Some(mut tmp) = current.take() {
            // current就是当前节点的下一个节点
            current = tmp.next.take();
            // 因为上面已经将当前节点的下一个节点保存在current变量中，所有当前的节点可以换成上一个结果节点
            tmp.next = res.take();
            // 结果节点更新为最新的节点
            res = Some(tmp);
        }
        res
    }
}

take()方法

take()方法将原值从Option中移除，保留None。我们在上面的题解中可以看到多处使用take()方法，我们来看一下tmp变量是如何从current链表获取值的。

while let Some(mut tmp) = current.take() {
  //...
}

此处将tmp设置为可变变量是因为下面有对tmp的修改。tmp的类型是Box<ListNode>。

mem::replace()方法

通过查看Option中take方法可以看到，它其实使用mem::replace()实现替换值

#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
#[rustc_const_unstable(feature = "const_option", issue = "67441")]
pub const fn take(&mut self) -> Option<T> {
    // FIXME replace `mem::replace` by `mem::take` when the latter is const ready
    mem::replace(self, None)
}

mem::replace是将src移到被引用的dest中, 并返回之前的dest的值。这两个值都不会被丢弃。

pub fn replace(dest: &mut T, src: T) -> T

use std::mem;
let mut v: Vec<i32> = vec![1,2];
let old_v = mem::replace(&mut v, vec![3,4,5]);
assert_eq!(vec![1, 2], old_v);
assert_eq!(vec![3, 4, 5], v);

所以上面take的self设置为&mut就是为了符合mem::replace中src的参数类型

mem::replace是通过ptr::read和ptr::write看到这里因为涉及到了内存管理，没怎么看明白，感兴趣的同学可以按照这个思路继续深入了Rust这些方法的具体实现，深入理解可以让我们运用自如。

通过算法学习rust之反转链表

知识点列举

解题思路

take()方法

mem::replace()方法

参考链接