добрый день, не могли бы подсказать, как можно развернуть связный список? Нужно на 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("развернуть список")
Чтобы обратить порядок элементов в связном списке за линейное время (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)
[/apcode]
