172 похожих чатов

Вот такой есть код, переворачивает связный список в интервале. #[derive(PartialEq, Eq,

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>> избавиться от третьего цикла в коде?

9 ответов

16 просмотров

Такое лучше кидать в code или на pastebin

это вроде с кодварс задачка да? Дай номер я вроде решал когда-то

Alexey- Автор вопроса

кажется что нельзя. У тебя иначе в какой-то момент получается мутабельная ссылка на кусок головы куда ты хочешь клеить реверс список (в твоем примере нода с (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 }

Αλεχ Zhukovsky
> без ансейфа

Ты уже написал, почему без ансейфа нельзя

Похожие вопросы

Обсуждают сегодня

Господа, а что сейчас вообще с рынком труда на делфи происходит? Какова ситуация?
Rꙮman Yankꙮvsky
29
А вообще, что может смущать в самой Julia - бы сказал, что нет единого стандартного подхода по многим моментам, поэтому многое выглядит как "хаки" и произвол. Короче говоря, с...
Viktor G.
2
30500 за редактор? )
Владимир
47
а через ESC-код ?
Alexey Kulakov
29
Гайс, вопрос для разносторонее развитых: читаю стрим с юарта, нада выделять с него фреймы с определенной структурой, если ли чо готовое, или долбаться с ринг буффером? нада у...
Vitaly
9
Чёт не понял, я ж правильной функцией воспользовался чтобы вывести отладочную информацию? но что-то она не ловится
notme
18
У меня есть функция где происходит это: write_bit(buffer, 1); write_bit(buffer, 0); write_bit(buffer, 1); write_bit(buffer, 1); write_bit(buffer, 1); w...
~
14
Добрый день! Скажите пожалуйста, а какие программы вы бы рекомендовали написать для того, чтобы научиться управлять памятью? Можно написать динамический массив, можно связный ...
Филипп
7
Недавно Google Project Zero нашёл багу в SQLite с помощью LLM, о чём достаточно было шумно в определённых интернетах, которые сопровождались рассказами, что скоро всех "ибешни...
Alex Sherbakov
5
длина пакета фиксированная, или меняется?
Okhsunrog
7
Карта сайта