Good afternoon, could you tell me how to expand a linked list? Need to 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 answer 1

    To reverse the order of elements in a linked list in linear time ( O(n) ), a lot of code is not required:

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

    The code in the loop cuts off the head of the list (head / car), adding to it the tail (tail) - the head.next = tail part. Then the tail builds up (the new tail points to the head just cut off with the old tail added) - the tail = head part. The rest of the list (head.next/cdr) becomes a new head (head) - head = head.next part. Repeat to the end of the list - while head part.

    To better understand the code, I recommend step-by-step ( Forward> button) , paying attention to the values ​​of the head, tail local variables in the reverse_list() function.

    In Python, objects on the right = constructions are calculated before the actual assignment takes place, which is then performed from left to right (for example, you cannot swap head.next, head pair. Since head.next , coming after head on the left side of assignment, addressed already to the new modified head of the list).

    Full example:

     #!/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))

    Result :

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

    Essentially, Python code is a translation from a Lisp algorithm :

     (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)