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 ответов

13 просмотров

Такое лучше кидать в 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
> без ансейфа

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

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

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

Добрый вечер. Есть вопрос, а может и предложение. Был у меня диалог в другой группе о делфи и я задался вопросом: "А нельзя ли в делфи цвет //коментария и {комментария} сде...
Kraszx
24
Всем привет! Подскажи, пожалуйста, как передать в TComboBox сразу значение и id записи. На Delphi я делал так: ComboBox1.Items.AddObject('Какое-то значение', Pointer(id запис...
Евгений
13
Мдя, прикол, боевая сборка запускается (именно под отладчиком) после F9 примерно полторы минуты (97 секунд если быть точным). Начал копать - проблема детектится сразу - зависа...
Александр (Rouse_) Багель
38
Здравствуйте, вопрос по структурам данных. Были у вас случаи, когда пришлось писать деревья или двунаправленные списки?
/ /
50
Товарищи, кто работа с iphelper? Или может я в самой логике ошибки фигачу, не пойму.... var ifTable : PMIB_IFTABLE; size, corSize: DWORD; Buffer ...
Warfarellen
4
я так понимаю, я так подозреваю, что создание такого плагина для человека, кто умеет писать плагины для делфи потребует минут 5-10 времени. но это мое подозрение. хотелось бы ...
Kraszx
7
Коллеги, добрый вечер. Создаю коллекцию от TFPGMap, ключ - перечисление, значение - целое. Нужно отсортировать коллекцию по значению. Как это можно сделать?
Kirill Filippenok
11
Скажи а ты когда этот канал создавал ты уже дельфи не любил, или это со временем пришло?
Роман Лях (rgreat)
18
Привет, такой вопросик появился кажется ли вам что Rust слишком сложный/строгий для высокоуровневого программирования и слишком "безопасный"/строгий для низкоуровневого?
Крокант
10
Всем привет! Использую кастомное модальное диалоговое окошко, все по классике - mrOK, mrCancel как ModalResult. Однако есть нюанс - в главной форме есть универсальный обработч...
Олег Гранишевский
20
Карта сайта