Rust踩雷笔记（7）——两个链表题例子初识裸指针

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: Option>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn reverse(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        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: Option<Box<ListNode>>) -> 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 Option> as * mut  Option>;
        let s = slow as *const Option<Box<ListNode>> as *mut Option<Box<ListNode>>;
        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
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

主要注意代码中的

let s = slow as *const Option<Box<ListNode>> as *mut Option<Box<ListNode>>;
let mut head2 = unsafe {
    (*s).take()
};
1
2
3
4

这里我的本意是写成这样：

let mut head2 = slow.take();
1

但是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
1
2

大意就是slow不是可变借用，take()的作用是拿走物主对某个东西的所有权，然后将所有权交给另一个人。你借一个人的东西，并且不被允许改变这个东西，那么你肯定不能把这个东西的所有权扔给别人对吧。

这个时候就需要裸指针的概念了，如果不会请移步：
https://kaisery.github.io/trpl-zh-cn/ch19-01-unsafe-rust.html
链接中截图关键内容：

注意*const和*mut是不可变、可变两种裸指针，星号不是解引用，而是类型的一部分。⚠️注意是将不可变引用变成*const类型的裸指针，可变引用变成*mut类型的裸指针，所以前面的代码里写的是：

let s = slow as *const Option<Box<ListNode>> as *mut Option<Box<ListNode>>;
1

slow是不可变引用&Option>，所以先转换为*const Option>，再转换为*mut Option>类型。

然后要在unsafe代码块中使用它，记得写法是(*s).take()拿到所有权赋给head2

let mut head2 = unsafe {
    (*s).take()
};
1
2
3

至此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: Option>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        // 从头结点开始向后走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 Option<Box<ListNode>> as *mut Option<Box<ListNode>>;
        let mut temp = unsafe {
            (*temp1).take()
        };
        // 我们需要将need_take的所有权赋给delete_next节点的next，所有权现在给了temp
        
        // delete_next是不可变引用，我们要修改它引用的节点的next，就可以通过可变裸指针
        // 不可变引用需要先转换为*const再转换为*mut
        let mut delete_next_temp = delete_next as *const Option<Box<ListNode>> as *mut Option<Box<ListNode>>;
        unsafe {
            (*delete_next_temp).as_mut().unwrap().next = temp;
        }
        dummy.unwrap().next
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54