时间戳

首页 > 解决方案 > 如何拆分给定的链表

rust - 如何拆分给定的链表

问题描述

我得到链表节点结构如下：

#[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()- 我失去了头脑。我不知道如何保持它。有人可以建议吗？

标签： rustlinked-list

解决方案

您的算法有效，问题在于take()从选项中删除了值并保留None在其位置。相反，您希望引用 中的值Option，因此您可以遍历列表而不改变它。这是由.as_ref()and完成的.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)
}

与测试用例的游乐场链接

推荐阅读