如何仅使用指针修改链表

Question

我有一个

Option<Box<ListNode>>

类型的链表，这个列表的一个节点包含两个属性：value（i32）和next（

Option<Box<ListNode>>

）。我创建了一个指针向量（

Vec<&Box<ListNode>>

），其目的是修改原始列表，如下图所示：

注意：结果列表应该是：

L: 1 -> 2 -> n-1 -> n

这是我的代码，它需要一些修复，但目前我需要知道是否可以使用指针修改我的链表。

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  pub fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}

pub fn delete_duplicates(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    head.as_ref()?;

    type NodeRef<'a> = &'a Box<ListNode>;
    type OptNodeRef<'a> = Option<NodeRef<'a>>;

    const MAX_NODES: u16 = 300;
    // let mut head = head;
    let mut current: OptNodeRef = head.as_ref();
    let mut node_ref: OptNodeRef = None;
    let mut vec_ref: Vec<NodeRef> = Vec::with_capacity(MAX_NODES as usize);
    let mut counter: u16 = 0;

    while let Some(node) = current {
        if node_ref.is_none() || node_ref.unwrap().val != node.val {
            node_ref = Some(node);
            if counter > 0 { 
                vec_ref.push(node);
            }
            counter = 0;
        } else {
            counter += 1;
        }

        current = node.next.as_ref();
    }
    
    if counter > 0 {
        vec_ref.push(node_ref.unwrap());
    }
    // vec_ref.into_iter().map(|t| t.val).for_each(|e| println!("{:?}", e));

    // my problem starts from here...
    for i in 0..vec_ref.len() - 1 {
        vec_ref[i].next = Some(*vec_ref[i + 1]);
    }

    if let Some(last_node) = vec_ref.last() {
        last_node.next = None;
    }

    if let Some(first_node) = vec_ref.first() {
        Some(**first_node)
    } else {
        None
    }
}

如何获得？我尝试了一些方法，但总是收到与借用、移动、不匹配错误相关的错误。修改“下一个”属性似乎很简单，但我没有主意。

Answer 1

第一个问题：

error[E0594]: cannot assign to data in an index of `Vec<&Box<ListNode>>`
  --> src/main.rs:51:9
   |
51 |         vec_ref[i].next = Some(*vec_ref[i + 1]);
   |         ^^^^^^^^^^^^^^^ cannot assign
   |
   = help: trait `IndexMut` is required to modify indexed content, but it is not implemented for `Vec<&Box<ListNode>>`

这里的错误消息可能有点晦涩，但本质上是因为您试图更改

Vec

中的项目，但这些项目位于

&

引用后面，因此它们不可变。您需要将类型从

Vec<&Box<ListNode>>

更改为

Vec<&mut Box<ListNode>>

。

然而，这样做会引发一系列其他问题，这些问题是由于您将持有对同一对象的多个可变引用而引起的，而这在 Rust 中是不允许的。

如果您的目的是删除彼此相邻的重复项，那么我认为这段代码可以大大简化。特别是，您不需要额外的

Vec

：我只需修改链表即可，如下所示：

pub fn delete_duplicates(head: &mut Option<Box<ListNode>>) {
    let mut node = head.as_mut();
    while let Some(this) = node {
        if let Some(ref mut next) = this.next {
            if this.val == next.val {
                this.next = next.next.take();
            }
        }
        node = this.next.as_mut();
    }
}