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

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

Для переворота связанного списка в Python вы можете использовать следующий код:


class Node:
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None

    def reverse(self):
        prev = None
        current = self.head
        while current:
            next = current.next
            current.next = prev
            prev = current
            current = next
        self.head = prev

Чтобы проверить работу кода, вы можете создать связанный список и применить метод reverse():


# Создание связанного списка
linked_list = LinkedList()
linked_list.head = Node(1)
second = Node(2)
third = Node(3)

linked_list.head.next = second
second.next = third

# Печать исходного связанного списка
print("Исходный связанный список:")
temp = linked_list.head
while temp:
    print(temp.data)
    temp = temp.next

# Переворот связанного списка
linked_list.reverse()

# Печать перевернутого связанного списка
print("Перевернутый связанный список:")
temp = linked_list.head
while temp:
    print(temp.data)
    temp = temp.next

Этот код создает связанный список с элементами 1, 2 и 3. Затем метод reverse() переворачивает список. Результатом будет перевернутый связанный список, содержащий элементы 3, 2 и 1.

Детальный ответ

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

Перевернуть связанный список в Python можно с помощью различных подходов. В этой статье мы рассмотрим один из наиболее эффективных способов - использование трех указателей.

Шаги для переворачивания списка

Инициализируйте три указателя: предыдущий (prev), текущий (curr) и следующий (next) указатели.
Установите предыдущий указатель в None и текущий указатель на голову списка.
Пока текущий указатель не будет равен None, выполняйте следующие действия:


while curr is not None:
    next = curr.next  # Сохраняем следующий узел
    curr.next = prev  # Переворачиваем указатель на следующий узел
    prev = curr  # Передвигаем указатель prev на текущий узел
    curr = next  # Передвигаем указатель curr на следующий узел

Разбор кода

В начале мы инициализируем указатели - prev, curr и next. У нас есть head, который указывает на начало списка. Предыдущий указатель prev устанавливаем в None, поскольку мы начинаем с пустого списка. Затем мы устанавливаем текущий указатель curr равным голове списка.

Затем мы переходим к основной части кода, где выполняется переворот списка. В цикле, пока текущий указатель curr не станет None, мы выполняем следующие шаги:

Сохраняем указатель на следующий узел, чтобы не потерять его.
Меняем указатель текущего узла на предыдущий узел, чтобы связь между узлами была перевернутой.
Передвигаем указатель prev на текущий узел.
Передвигаем указатель curr на следующий узел.

И так повторяется до тех пор, пока мы не дойдем до конца списка, то есть пока curr не станет None.

Пример кода


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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

# Пример использования
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)

reversed_head = reverse_linked_list(head)
# Вывод: 4 -> 3 -> 2 -> 1

Объяснение примера кода

В примере выше мы создаем связанный список с элементами 1, 2, 3 и 4. Затем мы вызываем функцию reverse_linked_list() и передаем голову списка в качестве аргумента. Функция возвращает новую голову списка, которая будет указывать на перевернутый список.

Вывод перевернутого списка - 4 -> 3 -> 2 -> 1.

Заключение

Мы рассмотрели один из эффективных способов перевернуть связанный список в Python. Используя трех указателей - prev, curr и next, мы успешно перевернули связи между узлами списка. Пример кода поможет вам лучше понять процесс переворачивания списка и применить его в своих проектах.

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