外包软件,西安seo服务,网站收录查询工具,360建筑网登录目录 leetcode 234leetcode 19 leetcode 234
题目在这https://leetcode.cn/problems/palindrome-linked-list/#xff0c;leetcode 234的回文链表#xff0c;思路很简单#xff0c;就是fast和slow两个指针#xff0c;fast一次移动两个、slow一次一个#xff0c;最后slow指… 目录 leetcode 234leetcode 19 leetcode 234
题目在这https://leetcode.cn/problems/palindrome-linked-list/leetcode 234的回文链表思路很简单就是fast和slow两个指针fast一次移动两个、slow一次一个最后slow指向的链表反转后和head比较就行了。
很简单一题但考虑一个问题slow和fast是什么形式由于rust有所有权机制所以slow和fast只能是借用并且还不能是可变借用可变借用只能有一个、可变借用和不可变借用不能同时存在。
所以slow和fast只能是两个不可变借用直接放上代码
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: OptionBoxListNode
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) - Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {pub fn reverse(mut head: OptionBoxListNode) - OptionBoxListNode {let mut prev None;while let Some(mut node) head {head node.next;node.next prev;prev Some(node);}prev}pub fn is_palindrome(head: OptionBoxListNode) - bool {// 快慢指针fast一次移动2个slow一次移动1个slow会停留在中间偏后的位置// 反转slow为头结点的链表// 比较head和slow两个链表直到head的长度达到即停止let p head.as_ref().unwrap();if p.next.is_none() {return true;}let mut head head;let mut slow head;let mut fast head;while slow.is_some() fast.is_some() {slow (slow.as_ref().unwrap().next);fast (fast.as_ref().unwrap().next);if fast.is_none() {break;}fast (fast.as_ref().unwrap().next);}// let s slow as *const OptionBoxListNode as * mut OptionBoxListNode;let s slow as *const OptionBoxListNode as *mut OptionBoxListNode;let mut head2 unsafe {(*s).take()};head2 Solution::reverse(head2);let mut flag true;while let (Some(node1), Some(node2)) (head.as_ref(), head2.as_ref()) {if node1.val ! node2.val {flag false;break;}head head.unwrap().next;head2 head2.unwrap().next;}flag}
}主要注意代码中的
let s slow as *const OptionBoxListNode as *mut OptionBoxListNode;
let mut head2 unsafe {(*s).take()
};这里我的本意是写成这样
let mut head2 slow.take();但是slow是不可变借用这里就会报错
cannot borrow *slow as mutable, as it is behind a reference
slow is a reference, so the data it refers to cannot be borrowed as mutable大意就是slow不是可变借用take()的作用是拿走物主对某个东西的所有权然后将所有权交给另一个人。你借一个人的东西并且不被允许改变这个东西那么你肯定不能把这个东西的所有权扔给别人对吧。
这个时候就需要裸指针的概念了如果不会请移步 https://kaisery.github.io/trpl-zh-cn/ch19-01-unsafe-rust.html 链接中截图关键内容 注意*const和*mut是不可变、可变两种裸指针星号不是解引用而是类型的一部分。⚠️注意是将不可变引用变成*const类型的裸指针可变引用变成*mut类型的裸指针所以前面的代码里写的是
let s slow as *const OptionBoxListNode as *mut OptionBoxListNode;slow是不可变引用OptionBoxListNode所以先转换为*const OptionBoxListNode再转换为*mut OptionBoxListNode类型。
然后要在unsafe代码块中使用它记得写法是(*s).take()拿到所有权赋给head2
let mut head2 unsafe {(*s).take()
};至此head2就是slow引用的那个节点了。
leetcode 19
题目是删除链表中倒数第n个节点要求一趟遍历。
这里也可以使用裸指针只要是如下场景都可以考虑裸指针 1和mut同时出现又不可避免。那么如果已经有了还需要一个mut的话可以创建裸指针mut 2需要通过不可变引用进行改变那么可以将转换为const再转换为*mut此时就和mut作用一致了。
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: OptionBoxListNode
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) - Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {pub fn remove_nth_from_end(head: OptionBoxListNode, n: i32) - OptionBoxListNode {// 从头结点开始向后走n - 1步let mut dummy Some(Box::new(ListNode::new(0)));dummy.as_mut().unwrap().next head;let mut p_tail (dummy.as_ref().unwrap().next);let mut cnt 0; // 向后走了几步while cnt n - 1 {cnt 1;p_tail (p_tail.as_ref().unwrap().next);}let mut delete_next dummy;while p_tail.as_ref().unwrap().next.is_some() {p_tail (p_tail.as_ref().unwrap().next);delete_next (delete_next.as_ref().unwrap().next);}// 至此我们只需要删除delete_next节点的下一个节点// 然后返回dummy的下一个节点即可// 通过裸指针拿到delete_next节点的下一个的下一个节点的所有权let mut need_take (delete_next.as_ref().unwrap().next);need_take (need_take.as_ref().unwrap().next);// need_take是不可变引用先拿到*mut类型的裸指针便可拿到need_take引用的节点所有权let mut temp1 need_take as *const OptionBoxListNode as *mut OptionBoxListNode;let mut temp unsafe {(*temp1).take()};// 我们需要将need_take的所有权赋给delete_next节点的next所有权现在给了temp// delete_next是不可变引用我们要修改它引用的节点的next就可以通过可变裸指针// 不可变引用需要先转换为*const再转换为*mutlet mut delete_next_temp delete_next as *const OptionBoxListNode as *mut OptionBoxListNode;unsafe {(*delete_next_temp).as_mut().unwrap().next temp;}dummy.unwrap().next}
}
