..

通过算法学习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 merge_two_lists(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    }
}

知识点列举

  • as_mut() 方法
  • 所有权之Move
  • ref 关键字

解题思路

impl Solution {
    pub fn merge_two_lists(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let (mut l1, mut l2) = (l1, l2);

        if l1.is_none() {
            return l2;
        }
        if l2.is_none() {
            return l1;
        }
        let mut res: Option<Box<ListNode>> = Some(Box::new(ListNode{next: None, val: 0}));
        let mut ans = res.as_mut(); // 这个变量是为了保存当前链表最后一个元素
        while l1.is_some() && l2.is_some() {
            let mut cur: Option<Box<ListNode>> = None;
            if l1.as_ref().unwrap().val <= l2.as_ref().unwrap().val {
                let next = l1.as_mut().unwrap().next.take();
                cur = l1;
                l1 = next;
            } else {
                let next = l2.as_mut().unwrap().next.take();
                cur = l2;
                l2 = next;
            }

            ans.as_mut().unwrap().next = cur;
            ans = ans.unwrap().next.as_mut();
        }

        if l1.is_some() {
            ans.as_mut().unwrap().next = l1;
        } else {
            ans.as_mut().unwrap().next = l2;
        }
        res.unwrap().next
    }
}

as_mut()方法

这里的链表题目我们可以看到使用了大量的as_mut()方法，我就就此来讨论一下，为什么要使用as_mut()方法以及as_mut()是如何实现的。

题目中有两个入参l1和l2，解决方案中要修改l1和l2，修改l1和l2的目的是为了剔除已经使用过的链表中节点

as_mut方法返回l1和l2 Option内部包含的数据的可变引用，as_mut的调用必须保证Option本身或者其引用是可变的, 我们通过保存变量并设置mut关键字的方式，让入参变成可变变量，这样就不需要修改入参的类型

我们可以分析题目中的使用场景，来解答为什么需要使用as_mut()。

let next = l1.as_mut().unwrap().next.take();
cur = l1;

我们需要将l1中next节点保存在next变量中，我们通过Option中的take()可以获取到next的值，同时我们也修改了l1变量，所以我们需要l1是可变变量。

let mut l1 = l1;

Move

Rust中以下操作会发生资源的移动（Move）

  • 赋值操作
  • 通过值来传递函数的参数
  • 函数返回数据
let next = l1.as_mut().unwrap().next.take();

上面代码进行了赋值操作，所有权发生了转移，在移动资源之后，原来的所有者不能再被使用，这可避免悬挂指针（dangling pointer）的产生。

如果我们不使用as_mut()，Rust编译器会报错。

let next = l1.unwrap().next.take();
// `l1` moved due to this method call
cur = l1; // value used here after move

由此可见Option中as_mut()的主要作用就是为了获取可变变量的引用，来避免资源移动后产生的垂悬引用的问题。

as_mut 的实现

实现的结果 &mut Option<T> -> Option<&mut T>

#[inline]
#[rustc_const_stable(feature = "const_option_basics", since = "1.48.0")]
#[stable(feature = "rust1", since = "1.0.0")]
pub const fn as_mut(&mut self) -> Option<&mut T> {
  match *self {
    Some(ref mut x) => Some(x),
    None => None,
  }
}

上面代码的match匹配值的模式，是rust中的match 解构

as_mut的入参类型是&mut self，这也是上面我们说的调用必须保证Option本身或者其引用是可变的.

match *self我们获取到的是&mut self这个可变引用指向的值, 如果我们不使用match *self进行的匹配的话，我们需要这样做（两种方式是相同的）

pub const fn as_mut(&mut self) -> Option<&mut T> {
  match self {
    &Some(ref mut x) => Some(x),
    None => None,
  }
}

ref mut x

当我们需要绑定的是被匹配对象的引用时，可以使用ref关键字。

// 赋值语句中左边的 `ref` 关键字等价于右边的 `&` 符号。
let ref ref_c1 = c;
let ref_c2 = &c;

// 如果一开始就不用引用，会怎样？ `reference` 是一个 `&` 类型，因为赋值语句
// 的右边已经是一个引用。但下面这个不是引用，因为右边不是。
let _not_a_reference = 3;

// Rust 对这种情况提供了 `ref`。它更改了赋值行为，从而可以对具体值创建引用。
// 下面这行将得到一个引用。
let ref _is_a_reference = 3;

因为我们最终的目的是要将&mut Option<T>变为Option<&mut T>，所以我们需要的是match匹配对象的可变引用。

在Some(ref mut x) => Some(x)中我们通过ref mut两个关键字来创建一个match匹配到的对象的可变引用，最终Some(x)的类型就是Option<&mut T>。

这里还需要注意的是我们通过Some()创建了一个新的Option

总结

上述的所有知识点都是通过学习分析as_mut方法扩展开来的，我们为什么要用as_mut()，因为如果不用as_mut的话在此题目中会产生所有权问题。产生Move的三个场景赋值操作、通过值来传递函数的参数、函数返回数据，由此我们可以了解到使用as_mut就是为了获取可变变量的引用，来避免资源移动后产生的垂悬引用的问题。

同时我们通过学习as_mut的实现，学习了match 解构、ref关键字，以及如何将&mut Option<T>转化为Option<&mut T>。

希望通过这些知识点的挖掘和学习，让我们对所有权系统知根知底，无畏所有权。

参考链接

Tags: [ linklist  rust  ]