代码之家  ›  专栏  ›  技术社区  ›  Evgeni Nabokov

如何拆分给定的链表

  •  0
  • Evgeni Nabokov  · 技术社区  · 4 年前

    #[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() -我失去了理智。我不知道如何保存它。

    0 回复  |  直到 4 年前
        1
  •  2
  •   Gurwinder Singh    4 年前

    你的算法有效,问题是 take() None 取而代之的是。相反,您希望在 Option ,因此您可以遍历列表而无需对其进行修改。这是由 .as_ref() .as_mut() ,返回哪个 Option<& (mut) T> ,其中参考点指向原件 T 并获得列表尾部的所有权。

    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