这个用于从未排序链表中删除重复项的 Rust 代码在 else 分支的低级别上执行什么操作？

Question

我有一个链接列表：

pub struct Node<T> {
    val: T,
    next: Option<Box<Node<T>>>
}

pub struct LinkedList<T> {
    head: Option<Box<Node<T>>>
}

我的问题涉及这个删除重复项的功能：

impl<T: Clone + Eq + Hash> LinkedList<T> {
    pub fn remove_dupes(&mut self) {
        let mut set = HashSet::new();
        let mut current = &mut self.head;
        while let Some(mut node) = current.take() { // AO
            if set.contains(&node.val) {
                *current = node.next.take();
            } else {
                set.insert(node.val.clone());
                let next = node.next.take(); // A1 take rest of list. Node.next is now None
                *current = Some(node); // A2 restore ownership of node to current but its now pointing to None.
                 current = &mut current.as_mut().unwrap().next; // *A3* None because (A1) took ownership. *Why is this line necessary?*
                *current = next; // A4 move to next node to continue with rest of list
            }
        }
    }

它的工作原理和删除欺骗就像下面一样，以更容易理解的方式：

impl<T: Clone + Eq + Hash> LinkedList<T> {
    pub fn remove_dupes(&mut self) {
        let mut set = HashSet::new();
        let mut current = &mut self.head;
        while let Some(mut node) = current.take() //B0 {
            if set.contains(&node.val) {
                *current = node.next.take();
            } else {
                set.insert(node.val.clone());
                *current = Some(node); // B1
                 current = &mut current.as_mut().unwrap().next; // B2
            }
        }
    }

我是 Rust 新手，正在努力了解内存中发生的事情。我不明白 A3 行需要什么 -

current = &mut current.as_mut().unwrap().next;

- 以及它真正在做什么，但如果没有它，该功能就无法工作。有人可以吗

1. 详细说明第一个函数中发生的情况，以及为什么它可以将所有权恢复到当前并移动到下一个节点？
2. 解释为什么 self.head 在函数返回后仍然指向列表的原始头，但指向列表的末尾（无），如果

   current = &mut current.as_mut().unwrap().next

   行在 A3 行中被注释掉。

我在这里有一个带有代码的游乐场（打印调试语句有点吵）：https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=0015a922b6cc0f7284c9b37d0dfb95e6

我的理解如下，可能有错误：

1.  while let Some(mut node) = current.take()

   (A0) 该行在循环的每次迭代中获取 current 的所有权，并将其赋予变量“node”。结果

   current

   为 None。

2. let next = node.next.take();

   (A1) 此行获取 node.next 的所有权并将其存储在变量

   next

   中以供以后使用。结果

   node.next

   为 None。

3. *current = Some(node);

   (A2) 再次将电流指向节点。当前不再是无。它现在指向 Node { val: (无论当前值是什么), next: None}

4. current = &mut current.as_mut().unwrap().next;

   (A3) 如果没有这一行，循环仍然会前进，但当函数返回到调用者时，链表最终将指向列表的末尾（无）。此处

   current.as_mut().unwrap().next;

   的值应始终为 None，因为我们从 A1 中的 node.next 中夺走了所有权。

5. *current = next;

   (A4) 将 current 指向我们存储在 A1 中的

   next

   中的下一个节点。

请注意，注释掉倒数第 2 行 (A3) 相当于

    pub fn remove_dupes(&mut self) {
        let mut set = HashSet::new();
        let mut current = &mut self.head;
        let mut restore:&mut Option<Box<Node<T>>> = &mut None;
        while let Some(mut node) = current.take() {
            if set.contains(&node.val) {
                *current = node.next.take();
            } else {
                set.insert(node.val.clone());
                let next = node.next.take();
                *restore = Some(node);
                 current = &mut restore.as_mut().unwrap().next;
                *current = next;
            }
        }
    }

    pub fn remove_dupes(&mut self) {
        let mut set = HashSet::new();
        let mut current = &mut self.head;
        while let Some(mut node) = current.take() {
            if set.contains(&node.val) {
                *current = node.next.take();
            } else {
                set.insert(node.val.clone());
                let next = node.next.take();
                *current = Some(node);
                *current = next;
            }
        }
    }

在调用后打印链表（使用我的格式化程序）会导致 head == None:

LL(0): |None|

Answer 1

这里棘手的部分是，在

current = &mut current.as_mut().unwrap().next

行之后，

*current

确实是

None

，但是

current

没有值

None

，它是一个指向next的

指针

节点。

由于它是一个指针，我们不仅可以用它观察

next

，还可以改变它。基本上，我们将

current

作为指向节点中当前列表的指针。

如果我们省略这一行，

current

将始终指向

head

，并且应用于它的所有更改都将应用于

head

。因此，我们将在列表中前进，但只需更改

head

并删除所有节点，使

head

指向最后一个节点

None

。