LeetCode 82. 删除排序链表中的重复元素 II — Rust 实现

思路

核心思路是用一个 dummy 哑节点 + tail 指针构造新链表：

1. 遍历原链表，每次取出一个节点 node，记住它的值 val。
2. 往后跳过所有值等于 val 的节点：
   · 若跳过了 ≥1 个节点，说明 val 是重复值，丢弃 node。
   · 若没跳过任何节点，说明 val 只出现一次，保留 node，接到 tail 后面。
3. 最后返回 dummy.next。

关键点：用 tail: &mut Box 作为"新链表尾指针"，每次保留节点后 tail = tail.next.as_mut().unwrap() 向后移动；不保留时 tail 原地不动，下次覆盖它的 next。

代码

// 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_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut dummy = Box::new(ListNode::new(0));
        // tail 始终指向新链表当前最后一个节点
        let mut tail: &mut Box<ListNode> = &mut dummy;

        let mut cur = head;
        while let Some(mut node) = cur {
            let val = node.val;
            cur = node.next.take();   // 取出 node，cur 指向后续链表

            // 检查后续是否有与 val 相同的节点
            let mut is_dup = false;
            while cur.as_ref().map_or(false, |n| n.val == val) {
                is_dup = true;
                let mut n = cur.take().unwrap();
                cur = n.next.take();  // 丢弃 n
            }

            if !is_dup {
                // val 唯一，保留 node
                tail.next = Some(node);
                tail = tail.next.as_mut().unwrap();
            }
            // 若 is_dup，node 被 drop，tail 原地不动
        }

        dummy.next
    }
}

复杂度分析

· 时间复杂度：O(n)，每个节点只被访问常数次。
· 空间复杂度：O(1)，只使用了常数个额外指针（返回的新链表本身可视为原地重建）。

运行示例

输入：1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5

迭代 node.val is_dup 动作
1 1 false 接到 tail，tail 指向 1
2 2 false 接到 tail，tail 指向 2
3 3 true 丢弃（后续也是 3）
4 4 true 丢弃（后续也是 4）
5 5 false 接到 tail，tail 指向 5

输出：1 -> 2 -> 5 ✅

Rust 实现要点

1. node.next.take()：把 Option<Box> 中的 Box 所有权取出，留下 None，避免借用冲突，是 Rust 操作链表最常用的手法。
2. tail: &mut Box：用可变引用做游标，避免了复杂的 Rc<RefCell<…>>，且没有 unsafe。
3. cur.as_ref().map_or(false, |n| n.val == val)：条件借用是临时的，while 循环体中可以安全地对 cur 做 take()。