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

#python #python_3x #односвязный_список

добрый день, не могли бы подсказать, как можно развернуть связный список? Нужно на
python'e..

from typing import Iterable

class LinkedListNode:

    def __init__(self, data):
        self.data = data
        self.next = None  # type: LinkedListNode

    def link(self, node: 'LinkedListNode') -> None:
        self.next = node


class LinkedList:

    def __init__(self, values: Iterable):
        previous = None
        self.head = None
        for value in values:
            current = LinkedListNode(value)
            if previous:
                previous.link(current)
            self.head = self.head or current
            previous = current

    def __iter__(self):
        current = self.head
        while current:
            yield current.data
            current = current.next

    def reverse(self) -> None:
        print("развернуть список")

    

Ответы

Ответ 1

Чтобы обратить порядок элементов в связном списке за линейное время (O(n)), не требуется
много кода:

def reverse_list(head, tail=None):
    while head:
        head.next, tail, head = tail, head, head.next
    return tail


Код в цикле отсекает голову списка (head/car), добавляя к ней хвост (tail) — head.next = tail
часть. Затем хвост наращивается (новый хвост указывает на только что отсечённую голову
с добавленным старым хвостом) — tail = head часть. Остаток списка (head.next/cdr) становится
новой головой (head) — head = head.next часть. Повторяем до конца списка — while head
часть.

Чтобы лучше понять код, рекомендую по шагам пройти (кнопка Forward>), обращая внимание
на значения head, tail локальных переменных в reverse_list() функции.

В Питоне, объекты в правой части = конструкции вычисляются до того как фактическое
присваивание происходит, которое затем  выполняется слева направо (например, нельзя
поменять местами head.next, head пару. Так как head.next, идущий после head в левой
части присваивания, обращался бы уже к новой изменённой голове списка).

Полный пример:

#!/usr/bin/env python3
"""Reverse linked list."""


class Node:
    """Linked list is either None or a value and a link to the next list."""

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


head = Node(1, Node(2, Node(3, Node(4))))


def print_list(head, end='\n'):
    while head:
        print(head.data, end=' -> ' if head.next else '')
        head = head.next
    print(end=end)


print_list(head)


def reverse_list(head, tail=None):
    while head:
        head.next, tail, head = tail, head, head.next
    return tail


print_list(reverse_list(head))


Результат:

1 -> 2 -> 3 -> 4
4 -> 3 -> 2 -> 1


По сути Питон-код это перевод из Lisp алгоритма:

(define reverse-list (lambda (head tail)
  (if (null? head)
      tail
      (reverse-list (cdr head) (cons (car head) tail)))))

(reverse-list '(1 2 3 4) '())   
; -> (4 3 2 1)