Nagibator & Memo
Nagibator
Привет, Мемо. Только что побил свой собственный рекорд в жёстком марафоне на LeetCode – пять звезд за тридцать минут. Думаешь, сможешь перещеголять меня? Давай посмотрим, справится ли твоя точность с моей скоростью.
Memo
Крутая работа, впечатляет. Я больше за чистый, безбаговый код, чем за скорость, но померяться силами с тобой не против – дай задачу, посмотрим, кто быстрее до пяти звёзд доберётся.
Nagibator
Итак, вот вам классика: развернуть односвязный список на месте и вернуть новый заголовок. Пятизвездочный уровень, без дополнительной памяти, без фиктивных узлов. Кто первый закончит? Начинаем соревнование!
Memo
Конечно, вот классическое реверс на месте, без "мусорных" узлов и без дополнительной памяти, только три указателя: prev, curr и next. Идея в том, чтобы пройтись по списку, перенаправить указатель "next" каждого узла на предыдущий, и вернуть последний обработанный узел в качестве новой головы.
```
Node reverseLinkedList(Node head) {
Node prev = null
Node curr = head
while curr != null {
Node next = curr.next // запоминаем следующий узел
curr.next = prev // разворачиваем связь
prev = curr // продвигаем prev вперед
curr = next // продвигаем curr вперед
}
return prev // новая голова развернутого списка
}
```
Всё. Время – O(n), память – O(1). Поделись, как бы ты это оптимизировал или если тебе нужна рекурсивная версия. Удачи!
Nagibator
Отличный, чистый код, но я бы предложил небольшую модификацию: обработай пустые или одноэлементные списки в одну строку и добавь оптимизацию хвостовой рекурсии. Считаешь, что сможешь сделать лучше? Давай посмотрим, что у тебя получилось.
Memo
Это что, код? Зачем ты мне его скинул?
Nagibator
Отличное рекурсивное решение, надо сказать. Ты только что дал мне идеальный шпаргалку – без компромиссов: ни скорости лишней, ни памяти, без мутных узлов, просто чистая элегантность. Обязательно учту это в следующий раз. Готов посмотреть, кто реально способен залезть на вершину таблицы лидеров? Погнали.