講完智慧指標後，回到用頭插法解Leetcode 92
impl Solution {
pub fn reverse_between(
head: Option<Box<ListNode>>,
left: i32,
right: i32,
) -> Option<Box<ListNode>> {
if left == right || head.is_none() {
return head;
}
let mut dummy = Some(Box::new(ListNode { val: 0, next: head }));
let mut pre = &mut dummy;
for _ in 1..left {
pre = &mut pre.as_mut().unwrap().next;
}
// curr = B 段原頭
let mut curr: *mut ListNode = pre.as_mut().unwrap().next.as_mut().unwrap().as_mut();
for _ in 0..(right - left) {
unsafe {
// 拿出 curr.next
let mut node = (*curr).next.take().unwrap();
// tail 跳過 node
(*curr).next = node.next.take();
// node 插到 pre 後面
node.next = pre.as_mut().unwrap().next.take();
pre.as_mut().unwrap().next = Some(node);
}
}
dummy.unwrap().next
}
}
跑完A段後，我們在B段把原本&mut轉型成裸指標*mut
let mut curr: *mut ListNode = pre.as_mut().unwrap().next.as_mut().unwrap().as_mut();
pre.as_mut() // Option<&mut Box<ListNode>>
.unwrap() // &mut Box<ListNode>
.next // &mut Option<Box<ListNode>>
.as_mut() // Option<&mut Box<ListNode>>
.unwrap() // &mut Box<ListNode>
.as_mut() // Box<ListNode>::as_mut -> &mut ListNode // Box<ListNode>::as_mut -> &mut ListNode
let mut curr: *mut ListNode //&mut T 自動可轉裸指標 *mut T
複習一下借用檢查原則
同時允許多個不可變借用 &T
最多只能有一個可變借用 &mut T
1和2不能同時存在。
我們在B段一開始curr就把prev.next node借走了對這個節點有唯一控制權，但在頭插法要加在A段結尾pre.as_mut().unwrap().next，像是借出了兩個 &mut，編譯器無法證明安全。
//沒轉成raw pointer
let mut curr:&mut ListNode = pre.as_mut().unwrap().next.as_mut().unwrap().as_mut();
for _ in 0..(right - left) {
unsafe {
// 拿出 curr.next
let mut node = (*curr).next.take().unwrap();
// tail 跳過 node
(*curr).next = node.next.take();
// node 插到 pre 後面
node.next = pre.as_mut().unwrap().next.take();
pre.as_mut().unwrap().next = Some(node);
}
}
編譯器在編譯時無法獲取足夠資訊，預設是會擋下來
我們可以用unsafe請編譯器不要檢查這區塊內的寫的code，由撰寫者由撰寫者自己負責。
在 unsafe 區塊裡除了請編譯器不要檢查這區塊內的寫的code，還可以操作safe情況不能做的事：
解引用 raw pointer（*const T, *mut T）
呼叫 unsafe fn（如 FFI、某些標準庫內部函式）
實作 unsafe trait
存取/修改 static mut
使用 union 不安全欄位
有了這我們就能使用頭插法修改linked list
這題因為leetcode宣告的結構next Option<Box<ListNode>>所以必須用unsafe來避免編譯器檢查，說到這有沒有想到Rc<T>,RefCell<T>
// 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
}
}
}
Rc<T>,RefCell<T>修改unsafeuse std::cell::RefCell;
use std::rc::Rc;
#[derive(Clone, Debug)]
struct Node {
val: i32,
next: Option<Rc<RefCell<Node>>>,
}
impl Node {
fn new(val: i32) -> Rc<RefCell<Self>> {
Rc::new(RefCell::new(Node { val, next: None }))
}
}
fn from_vec(v: &[i32]) -> Option<Rc<RefCell<Node>>> {
let mut head: Option<Rc<RefCell<Node>>> = None;
for &x in v.iter().rev() {
let n = Node::new(x);
n.borrow_mut().next = head;
head = Some(n);
}
head
}
fn to_vec(mut head: Option<Rc<RefCell<Node>>>) -> Vec<i32> {
let mut out = Vec::new();
while let Some(rc) = head {
out.push(rc.borrow().val);
head = rc.borrow().next.clone();
}
out
}
fn reverse_between_rc(
head: Option<Rc<RefCell<Node>>>,
left: i32,
right: i32,
) -> Option<Rc<RefCell<Node>>> {
if left == right || head.is_none() {
return head;
}
// dummy node to simplify edge cases
let dummy = Rc::new(RefCell::new(Node { val: 0, next: head.clone() }));
let mut prev = Rc::clone(&dummy);
// Move prev to the node before 'left'
for _ in 0..(left - 1) {
let next = prev.borrow().next.clone().unwrap();
prev = next;
}
// Start reversing
let mut curr = prev.borrow().next.clone();
let mut prev_sub = None;
for _ in left..=right {
if let Some(node) = curr.clone() {
let next = node.borrow().next.clone();
node.borrow_mut().next = prev_sub;
prev_sub = Some(node);
curr = next;
}
}
// Connect the reversed part back
let left_node = prev.borrow().next.clone().unwrap();
left_node.borrow_mut().next = curr;
prev.borrow_mut().next = prev_sub;
// Return new head
dummy.borrow().next.clone()
}
fn main() {
let v = vec![1, 2, 3, 4, 5];
let head = from_vec(&v);
let new_head = reverse_between_rc(head, 2, 4);
let out = to_vec(new_head);
println!("{:?}", out); // [1, 4, 3, 2, 5]
}
use std::cell::RefCell;
use std::rc::Rc;
#[derive(Clone, Debug)]
struct Node {
val: i32,
next: Option<Rc<RefCell<Node>>>,
}
impl Node {
fn new(val: i32) -> Rc<RefCell<Self>> {
Rc::new(RefCell::new(Node { val, next: None }))
}
}
fn from_vec(v: &[i32]) -> Option<Rc<RefCell<Node>>> {
let mut head: Option<Rc<RefCell<Node>>> = None;
for &x in v.iter().rev() {
let n = Node::new(x);
n.borrow_mut().next = head;
head = Some(n);
}
head
}
fn to_vec(mut head: Option<Rc<RefCell<Node>>>) -> Vec<i32> {
let mut out = Vec::new();
while let Some(rc) = head {
out.push(rc.borrow().val);
head = rc.borrow().next.clone();
}
out
}
// 頭插法反轉 left~right 節點
fn reverse_between_rc(
head: Option<Rc<RefCell<Node>>>,
left: i32,
right: i32,
) -> Option<Rc<RefCell<Node>>> {
if left == right || head.is_none() {
return head;
}
// dummy node to簡化邊界
let dummy = Rc::new(RefCell::new(Node { val: 0, next: head.clone() }));
let mut prev = Rc::clone(&dummy);
// prev移到left-1
for _ in 0..(left - 1) {
let next = prev.borrow().next.clone().unwrap();
prev = next;
}
// start是left節點
let start = prev.borrow().next.clone().unwrap();
// 進行頭插法
for _ in left..right {
// 要移動的節點
let to_move = start.borrow().next.clone().unwrap();
// start.next 指向 to_move.next
start.borrow_mut().next = to_move.borrow().next.clone();
// to_move 插到 prev 後面
to_move.borrow_mut().next = prev.borrow().next.clone();
prev.borrow_mut().next = Some(to_move);
}
dummy.borrow().next.clone()
}
fn main() {
let v = vec![1, 2, 3, 4, 5];
let head = from_vec(&v);
let new_head = reverse_between_rc(head, 2, 4);
let out = to_vec(new_head);
println!("{:?}", out); // [1, 4, 3, 2, 5]
}
input = [1, 2, 3, 4, 5]
output = [1, 4, 3, 2, 5]
iThome鐵人賽
看影片追技術