Clone, Debug)]
pub struct ListNode {
pub val: i32,
pub next: Option<Box<ListNode>>,
}
pub fn reverse_between(
mut head: Option<Box<ListNode>>,
left: i32,
right: i32,
) -> Option<Box<ListNode>> {
let mut cur = &mut head;
let left = left - 1;
for _ in 0..left {
if let Some(node) = cur {
cur = &mut node.next;
} else {
return head;
}
}
let mut sub_head = None;
let mut sub_rest = cur.take();
for _ in left..right {
if let Some(mut node) = sub_rest {
sub_rest = node.next;
node.next = sub_head;
sub_head = Some(node);
}
}
*cur = sub_head;
for _ in left..right {
if let Some(node) = cur {
cur = &mut node.next;
}
}
*cur = sub_rest;
head
}
fn main() {
let list = make_list(&vec![1, 2, 3, 4, 5]);
let new_list = reverse_between(list, 2, 4);
let vec = list_to_vec(&new_list);
assert_eq!(vec, vec![1, 5, 4, 3, 2]);
}
Если взять мутабельную ссылку на sub_head, то можно было бы избавиться от третьего цикла. Но, борроу чекер не даст. Вопрос в целом такой - можно ли в safe rust и без Rc<RefCell<T>> избавиться от третьего цикла в коде?
Такое лучше кидать в code или на pastebin
это вроде с кодварс задачка да? Дай номер я вроде решал когда-то
это с leetcode https://leetcode.com/problems/reverse-linked-list-ii
кажется что нельзя. У тебя иначе в какой-то момент получается мутабельная ссылка на кусок головы куда ты хочешь клеить реверс список (в твоем примере нода с (1)) и на остальную часть списка. В итоге получается алиас на (2) в виде cur и head.next. Со слайсами это можно решить через split_at_mut - и получить регионы которые гарантированно не алиасятся. Но для произвольных линкедлистов этого нет конечно
pub type Link = Option<Box<ListNode>>; unsafe fn next(x: *mut ListNode) -> *mut *mut ListNode { std::ptr::addr_of_mut!((*x).next) as _ } fn null_checked<T: ?Sized>(ptr: *mut T) -> Option<*mut T> { (!ptr.is_null()).then(|| ptr) } pub fn rev(head: Link, left: i32, right: i32) -> Link { if right == 1 { return head; } let mut head = ListNode { val: 0, next: head }; let mut prev: *mut ListNode = &mut head; for _ in 1..left { prev = unsafe { null_checked(*next(prev))? }; } unsafe { let curr = null_checked(*next(prev))?; for _ in left..right { let n = null_checked(*next(curr))?; next(curr).write(*next(n)); next(n).write(*next(prev)); next(prev).write(n); } } head.next }
pub type Link = Option<Box<ListNode>>; unsafe fn next(x: *mut ListNode) -> *mut *mut ListNode { std::ptr::addr_of_mut!((*x).next) as _ } fn null_checked<T: ?Sized>(ptr: *mut T) -> Option<*mut T> { (!ptr.is_null()).then(|| ptr) } pub fn rev(head: Link, left: i32, right: i32) -> Link { let mut head = ListNode { val: 0, next: head }; let mut prev = &mut head; for _ in 1..left { prev = prev.next.as_deref_mut()?; } unsafe { let prev: *mut ListNode = prev; let curr = null_checked(*next(prev))?; for _ in left..right { let n = null_checked(*next(curr))?; next(curr).write(*next(n)); next(n).write(*next(prev)); next(prev).write(n); } } head.next }
Ты уже написал, почему без ансейфа нельзя
Обсуждают сегодня