是否可以在不分配任何节点的情况下就地反转链表？

Question

我试图了解 Rust 中的所有权如何与链表相关。我有这个代码：

struct Node {
    value: i32,
    next: Option<Box<Node>>
}

fn main() {
    let mut x = Box::new(Node {value: 1, next: None});
    let mut y = Box::new(Node {value: 2, next: Some(x)});
}

它创建了一个链表 y -> x -> null。是否可以就地切换，以便我们最终得到 x -> y -> null 而不分配任何新节点？

Answer 1

绝对地。在这种情况下，所有权非常简单：main函数拥有y，拥有x，所有者可以改变他们拥有的东西。

要交换两个节点a，并b在那里a？b? ...，您只需要执行以下操作：

• 断开b的a，让你有a？? 和b？……
• 删除以下所有内容b；叫这个c…。你现在有b吗？? 和c? …… 请注意，它c可能是空的，也可能是一个很长的列表；我们不在乎。
• a并且b现在是单独的，并且不连接到任何其他东西，因此您可以交换它们的内容，就地交换它们。
• 附在c最后a，给你a什么？c? ……
• 附在a最后b，给你b什么？a? ……

不需要分配新节点，这几乎可以直接转录到 Rust 中：

struct Node {
    value: i32,
    next: Option<Box<Node>>
}

impl Node {
    pub fn swap_with_next(&mut self) {
        use std::mem::swap;

        match self.next.take() {
            Some(mut next_node) => {
                let next_next = next_node.next.take();
                swap(self, &mut next_node);
                next_node.next = next_next;
                self.next = Some(next_node);
            },
            None => {
                // Uh-oh, there's nothing to swap *with*!
                panic!("cannot swap with nothing");
            }
        }
    }

    pub fn show(&self) {
        print!("{:?}", self.value);
        if let Some(next) = self.next.as_ref() {
            print!(" -> ");
            next.show();
        }
    }
}

fn main() {
    let mut w = Box::new(Node { value: 0, next: None });
    let mut x = Box::new(Node { value: 1, next: Some(w) });
    let mut y = Box::new(Node { value: 2, next: Some(x) });

    y.show();
    println!("");

    y.swap_with_next();
    y.show();
    println!("");
}

最后，如果我没有指出您使用完全太多的链表来学习 Rust，那我就是失职了。