TransWikia.com

How to split given linked list

Stack Overflow Asked by Evgeni Nabokov on December 18, 2020

I am given the linked list node struct as follows:

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

I need to write a method splitting a linked list equally and returning both parts. I could not make it in a single method, so I created two: the first calculates the length of the list, the second splits.

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);

The problem is in split() – I lose the head. I don’t how to keep it.
Could anybody advise?

One Answer

Your algorithm works, the problem is that take() removes the value from option and leaves None in its place. Instead, you want to have a reference to the value inside the Option, so you can traverse the list without mutating it. This is done by .as_ref() and .as_mut(), which return Option<& (mut) T>, where the reference points to the original T. Then once we have a reference to the second half, we take() out of it and get ownership of the tail of the list.

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

Correct answer by Lytigas on December 18, 2020

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP