Условие

Дано начало односвязного списка. Необходимо перевернуть список и вернуть его перевернутый вид.

Например, если дан список 1 -> 2 -> 3 -> 4 -> 5, то после переворота он станет 5 -> 4 -> 3 -> 2 -> 1.

Примеры

Пример 1:

Вход: 1 -> 2 -> 3 -> 4 -> 5

Выход: 5 -> 4 -> 3 -> 2 -> 1

Пример 2:

Вход: 1 -> 3 -> 5 -> 6 -> 7

Выход: 7 -> 6 -> 5 -> 3 -> 1

Решение

Для решения данной задачи необходимо пройти по списку, меняя местами указатели на следующий и текущий элементы. Для этого нужно завести три указателя: prev (None в начале), curr (начало списка) и next (curr.next).

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

Пример

Для списка 1 -> 2 -> 3 -> 4 -> 5:

1. prev = None, curr = 1, next = 2
2. curr.next = None, prev = 1, curr = 2, next = 3
3. curr.next = 1, prev = 2, curr = 3, next = 4