在 Rust 中反转双向链表

Question

我有以下双向链表的实现 ->

struct Node<T> {
    value: T,
    next: Option<Rc<RefCell<Node<T>>>>,
    prev: Option<Weak<RefCell<Node<T>>>>,
}

impl<T> Node<T> {
    fn new(value: T) -> Self {
        Node {
            value,
            next: None,
            prev: None,
        }
    }
}

impl<T> From<Node<T>> for Option<Rc<RefCell<Node<T>>>> {
    fn from(node: Node<T>) -> Self { Some(Rc::new(RefCell::new(node))) }
}

type NodePtr<T> = Rc<RefCell<Node<T>>>;

pub struct DoublyLinkedList<T> {
    head: Option<NodePtr<T>>,
    tail: Option<NodePtr<T>>,
}

但是，我很难实现反转链表的算法。

我试过了

    pub fn reverse(&mut self) {
        let mut current_node = self.head.clone();
        while let Some(current) = current_node {
            let mut current_borrowed = current.borrow_mut();
            std::mem::swap(&mut current_borrowed.next, &mut current_borrowed.prev);
            current_node = current_borrowed.prev.upgrade();
        }
        std::mem::swap(&mut self.head, &mut self.tail);
    }

但这不起作用，因为 current_borrowed.prev 是

Option<Weak<RefCell<Node<T>>>>

，而且我无法升级或降级

current_borrowed.next

。

Answer 1

您不能直接交换

next

和

prev

成员，因为它们不具有相同的类型。
但是，我们可以逐步交换，获取这些选项的内容（保留

None

），并在重新分配之前根据需要执行升级/降级。

    pub fn reverse(&mut self) {
        let mut current_node = self.head.clone();
        while let Some(current) = current_node {
            let mut current_borrowed = current.borrow_mut();
            let next = current_borrowed.next.take();
            let prev = current_borrowed.prev.take();
            if let Some(prev) = prev {
                current_borrowed.next = Some(prev.upgrade().unwrap());
            }
            if let Some(next) = &next {
                current_borrowed.prev =
                    Some(Rc::<RefCell<Node<T>>>::downgrade(next));
            }
            current_node = next;
        }
        std::mem::swap(&mut self.head, &mut self.tail);
    }

您还可以重复从该列表的尾部弹出并追加到新列表的尾部，然后交换两个列表。