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 = ¤t_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?
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)
}
Correct answer by Lytigas on December 18, 2020
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP