Проблема:
Обратить односвязный список.
Пример:
Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL
Мое решение:
def reverseList(head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
reverse_head = head
curr = head.next
reverse_head.next = None
while(curr is not None):
temp = curr.next
curr.next = reverse_head
reverse_head = curr
curr = temp
return reverse_head
Пояснение:
Я использовал итеративное решение для решения этой проблемы, просто чтобы избежать проблем с рекурсией, таких как переполнение стека.
Идея обращения списка довольно проста. У нас есть два списка, исходный и обратный. Мы удаляем каждый элемент из исходного списка и добавляем его в начало перевернутого списка. Таким образом, последний элемент в нашем исходном списке будет в верхней части перевернутого списка, а первый элемент в конце.
Итак, как мы можем сделать это со связанными списками?
Мы поддерживаем два указателя: один на начало перевернутого списка и один на текущую позицию исходного списка.
Сначала мы делаем резервную копию указателя next из нашего текущего элемента.
Затем мы делаем так, чтобы next нашего текущего элемента указывала на начало нашего перевернутого списка.
Затем мы корректируем заголовок нашего перевернутого списка, чтобы он указывал на наш текущий элемент.
Теперь, когда мы переместили наш текущий элемент в перевернутый список, мы повторно настраиваем наш текущий элемент на следующий элемент в исходном списке. (помните, мы сделали резервную копию этой (переменной temp)?
Мы повторяем это итеративно, пока не достигнем конца исходного списка.
После того, как мы полностью обработали исходный список, мы возвращаем заголовок перевернутого списка.
Вот и все! И вот как вы решаете проблему «Обратно связанного списка».
Если вы заинтересованы в решении других проблем, подписывайтесь на 60 Days of Coding и присоединяйтесь ко мне в этом путешествии.
Если вы хотите, чтобы я решил и объяснил какие-либо проблемы, добавьте их в комментарии вместе со ссылкой на описание проблемы.
Увидимся завтра!
Ваше здоровье!
