rust - 如何分割给定的链表

Question

我得到链表节点的结构如下:

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

我需要编写一个方法来平均拆分链表并返回两个部分。我无法用一种方法实现它，所以我创建了两个方法:第一个方法计算列表的长度，第二个方法拆分。

fn get_length(head: &Option<Box<ListNode>>) -> usize {
    let mut res = 0;
    let mut current_node = head;
    while current_node.is_some() {
        current_node = &current_node.as_ref().unwrap().next;
        res += 1;
    }
    res
}

fn split(mut head: Option<Box<ListNode>>, len: usize) -> (Option<Box<ListNode>>, Option<Box<ListNode>>) {
    let mut curr = head.take();
    for _ in 0..len {
        let mut curr_inner = curr.unwrap();
        curr = curr_inner.next.take();
    }
    (head, curr.take())
}

let len = get_length(&node);
let (l1, l2) = split(node, len / 2 + len % 2);

问题出在 split()中-我丢了头。我不怎么保留它。
有人可以建议吗？

Answer 1

您的算法有效，问题在于take()从选项中删除了值，并将None留在了它的位置。相反，您希望引用Option内部的值，因此可以遍历列表而无需对其进行更改。这是通过.as_ref()和.as_mut()完成的，它们返回Option<& (mut) T>，其中引用指向原始T。然后，一旦我们引用了下半部分，就将其从take()中取出，并获得列表尾部的所有权。

fn split(
    mut head: Option<Box<ListNode>>,
    len: usize,
) -> (Option<Box<ListNode>>, Option<Box<ListNode>>) {
    let mut curr = &mut head;
    for _ in 0..len {
        let curr_inner = curr.as_mut().unwrap();
        curr = &mut curr_inner.next;
    }
    let tail = curr.take();
    (head, tail)
}

Playground link with test case