题目

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。

示例1:

1
2
3
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例2:

1
2
3
输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

附上链接：剑指offer.18题(LeetCode地址)

解题

说明

这道题目如果用 c 或者 c++ 做非常简单
但是如果能用 Rust 实现且不使用unsafe模式
其实需要对 Rust 的指针、引用以及所有权机制有相对深刻的理解才行

个人首次尝试用 Rust 实现失败了，所以记录一下，深刻学习。

代码

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
// 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 delete_node(mut head: Option<Box<ListNode>>, val: i32) -> Option<Box<ListNode>> {
        let mut hcal = &mut head;

        // 关键点【1】
        while let Some(hp) = hcal {
            if hp.val == val {
                // 关键点【2】
                *hcal = hp.next.take();
                break;
            }
            // 关键点【3】
            hcal = &mut hcal.as_mut().unwrap().next;
        }

        return head;
    }
}

代码实现很短，但是却非常精练，值得学习和深思。

关键点【1】，需要思考：变量 hp 是什么类型？
因为 take() 方法至少需要 mut 才能调用，所以这里的 hp 类型应该是 &mut Box<ListNode> 类型

关键点【2】，需要思考： hcal: &mut Option<T> 作为一个指针/引用，它的解引用运算符此时表示的什么含义？
从结果来看，这里 *hcal 表示了指向当前节点的指针，也就是上一个节点的next

关键点【3】，需要思考：为什么这里要从类型 &mut Option<T> 到 Option<&mut T>的转化？
TODO

综上，理解这道题解法的关键就是：变量 hcal 是每一个节点中 next 字段的引用！！！