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

Алгоритм разворота односвязного списка

Разворот односвязного списка — это классическая задача на понимание работы с указателями и структур данных. Существует несколько подходов к решению, но наиболее распространённым и эффективным является итеративный метод с использованием трёх указателей.

Основные подходы к решению

1. Итеративный метод с тремя указателями Этот подход является оптимальным по памяти (O(1) дополнительной памяти) и времени (O(n)). Алгоритм проходит по списку один раз, меняя направление ссылок.

public class ListNode
{
    public int Value;
    public ListNode Next;
    
    public ListNode(int value)
    {
        Value = value;
        Next = null;
    }
}

public ListNode ReverseList(ListNode head)
{
    // Три указателя: предыдущий, текущий, следующий
    ListNode previous = null;
    ListNode current = head;
    ListNode next = null;
    
    while (current != null)
    {
        // Сохраняем следующую ноду перед разрывом связи
        next = current.Next;
        
        // Разворачиваем указатель текущей ноды
        current.Next = previous;
        
        // Сдвигаем указатели
        previous = current;
        current = next;
    }
    
    // Previous теперь указывает на новую голову списка
    return previous;
}

2. Рекурсивный метод Этот подход элегантен, но имеет ограничение по глубине рекурсии и использует стек вызовов:

public ListNode ReverseListRecursive(ListNode head)
{
    // Базовый случай: пустой список или одна нода
    if (head == null || head.Next == null)
        return head;
    
    // Рекурсивно разворачиваем оставшуюся часть
    ListNode newHead = ReverseListRecursive(head.Next);
    
    // Разворачиваем указатель текущей ноды
    head.Next.Next = head;
    head.Next = null;
    
    return newHead;
}

Пошаговое объяснение итеративного алгоритма

1. Инициализация указателей:

   • previous — изначально null (будет новой головой в конце)
   • current — начинаем с головы списка
   • next — временное хранение следующего элемента

2. Проход по списку:

   • На каждой итерации сохраняем current.Next в next
   • Меняем направление указателя: current.Next = previous
   • Сдвигаем previous на current
   • Сдвигаем current на сохранённый next

3. Завершение:

   • Когда current становится null, previous указывает на последнюю обработанную ноду
   • Возвращаем previous как новую голову списка

Особенности реализации в Unity/C#

В контексте разработки на Unity, вы можете столкнуться с особыми случаями:

• Работа с GameObject и компонентами: если список содержит ссылки на Unity-объекты, нужно учитывать возможность null-ссылок
• Многопоточность: при работе в многопоточном контексте требуется синхронизация
• Оптимизация для мобильных платформ: итеративный метод предпочтительнее из-за меньшего потребления стека

Тестирование решения

// Пример использования
void TestReverseList()
{
    // Создаем список: 1 -> 2 -> 3 -> 4 -> 5
    ListNode head = new ListNode(1);
    head.Next = new ListNode(2);
    head.Next.Next = new ListNode(3);
    head.Next.Next.Next = new ListNode(4);
    head.Next.Next.Next.Next = new ListNode(5);
    
    // Разворачиваем
    ListNode reversed = ReverseList(head);
    
    // Теперь: 5 -> 4 -> 3 -> 2 -> 1
    // Можно пройти по списку для проверки
    ListNode current = reversed;
    while (current != null)
    {
        Debug.Log(current.Value);
        current = current.Next;
    }
}

Сравнение подходов

Рекомендация: в большинстве случаев, особенно в продакшн-коде и геймдеве, предпочтительнее использовать итеративный метод из-за его предсказуемости по памяти и отсутствия риска переполнения стека. Рекурсивный метод хорош для демонстрации понимания рекурсии, но имеет практические ограничения на больших списках.

Это фундаментальный алгоритм, который проверяет понимание работы с указателями, структур данных и базовых алгоритмических концепций — важных навыков для любого разработчика, работающего с Unity и C#.