I am reversing a segment inside a linked list based on a start and end position. For example, reverse_between([1, 2, 3, 4, 5], 2, 4) would return [1, 4, 3, 2, 5].
I was able to solve it, but I'm not happy with my solution because I have to iterate over the middle segment twice:
- cut off the tail of the list after the middle segment
- reverse the middle segment by adding each element onto the front of the tail
From a language-independent perspective, I know that I should be able to just keep a reference to the beginning (soon-to-be end) of the middle chunk, and then when I'm done reversing, I would use that reference to append the tail and be done in one pass. However, a reference to any part of the tail of a linked list will make the Rust compiler refuse to let me modify the head.
Is it possible to solve this problem in one pass?
pub struct ListNode {
pub val: i32,
pub next: Option<Box<ListNode>>,
}
fn reverse_between(mut head: Option<Box<ListNode>>, m: i32, n: i32) -> Option<Box<ListNode>> {
let mut head_ptr = &mut head;
for _ in 1..m {
head_ptr = &mut head_ptr.as_mut().unwrap().next;
}
let mut middle = head_ptr.take();
let mut middle_ptr = &mut middle;
for _ in m..=n {
middle_ptr = &mut middle_ptr.as_mut().unwrap().next;
}
let mut tail = middle_ptr.take();
while let Some(mut x) = middle {
middle = x.next.take();
x.next = tail;
tail = Some(x);
}
std::mem::swap(head_ptr, &mut tail);
head
}
