tgoop.com/csharpproglib/6375
Last Update:
🔄 Как развернуть связный список
Дан связный список, нужно развернуть его задом наперёд. Разберём как решить задачу элегантно.
У вас есть цепочка узлов: 1 → 2 → 3 → 4 → 5. Каждый узел хранит значение и ссылку на следующий элемент. Задача — перевернуть все стрелки: 1 ← 2 ← 3 ← 4 ← 5.
Главная сложность здесь не в алгоритме, а в работе с указателями. Стоит перезаписать ссылку неправильно — и вы теряете доступ к остальной части списка. Именно поэтому многие решения проваливаются на первой попытке.
Итеративное решение: три указателя
Самый надёжный подход — использовать три указателя, которые двигаются по списку синхронно.
• prev отслеживает предыдущий узел
• curr указывает на текущий обрабатываемый узел
• next сохраняет следующий узел, чтобы не потерять его при развороте
Код:
public ListNode ReverseList(ListNode head)
{
ListNode prev = null;
ListNode curr = head;
while (curr != null)
{
ListNode next = curr.next; // сохраняем следующий
curr.next = prev; // разворачиваем стрелку
prev = curr; // двигаем prev
curr = next; // двигаем curr
}
return prev;
}
Рекурсивное решение
Если вам нравятся рекурсивные решения, есть и такой вариант:
public ListNode ReverseList(ListNode head)
{
if (head == null || head.next == null)
return head;
ListNode newHead = ReverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
Попробуйте решить задачу сами, прежде чем смотреть готовый код. Нарисуйте список на бумаге, отследите движение указателей вручную. Это единственный способ понять, что происходит.
#dotnet_challenge