Можете ли вы пошагово описать алгоритм решения данной задачи?

Разворот односвязного списка — это классическая задача на работу с указателями. Идея: мы проходим по списку один раз и для каждого узла меняем его ссылку на предыдущий узел. Чтобы не потерять доступ к остатку списка, сохраняем следующий узел перед перенаправлением. Алгоритм работает за O(n) времени и O(1) дополнительной памяти.

Пошаговое описание с кодом на Python:

1. Инициализация: prev = None, curr = head.
2. Пока curr не равен None:
   • next_temp = curr.next — сохраняем следующий узел.
   • curr.next = prev — разворачиваем указатель текущего узла на предыдущий.
   • prev = curr — сдвигаем prev вперёд.
   • curr = next_temp — переходим к сохранённому следующему узлу.
3. После цикла prev указывает на новую голову списка. Возвращаем prev.

def reverse_linked_list(head):
    prev = None
    curr = head
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    return prev

Пример для списка 1 → 2 → 3:

• Начало: prev=None, curr=1.
• Итерация 1: next=2, 1.next=None, prev=1, curr=2.
• Итерация 2: next=3, 2.next=1, prev=2, curr=3.
• Итерация 3: next=None, 3.next=2, prev=3, curr=None.
• Возвращаем prev=3. Список: 3 → 2 → 1.

Граничные случаи: если head = None, возвращаем None; если один элемент, цикл выполнится один раз и вернёт тот же узел. Сложность O(n), память O(1). Рекурсивный способ тоже возможен, но итеративный надёжнее — нет риска переполнения стека на длинных списках.