🔄 Как развернуть связный список

Дан связный список, нужно развернуть его задом наперёд. Разберём как решить задачу элегантно.

У вас есть цепочка узлов: 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