[PYTHON] Algorithmus Gymnastik 24 Eine verknüpfte Liste umkehren

Reverse a LinkedList Wenn Sie den Anfang einer einzelnen LinkedList angeben, wird die LinkedList umgekehrt. Schreiben Sie eine Funktion, die einen neuen Kopf für die invertierte LinkedList zurückgibt.

Beispiel

Solution Sie können die drei Zeiger "Zurück", "Aktuell" und "Weiter" verwenden, um die LinkedList in einer einzigen Iteration umzukehren.

Implementierung

from __future__ import print_function


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

  def print_list(self):
    temp = self
    while temp is not None:
      print(temp.value, end=" ")
      temp = temp.next
    print()


def reverse(head):
  previous, current, next = None, head, None
  while current is not None:
    next = current.next  # temporarily store the next node
    current.next = previous  # reverse the current node
    previous = current  # before we move to the next node, point previous to the current node
    current = next  # move on the next node
  return previous


def main():
  head = Node(2)
  head.next = Node(4)
  head.next.next = Node(6)
  head.next.next.next = Node(8)
  head.next.next.next.next = Node(10)

  print("Nodes of original LinkedList are: ", end='')
  head.print_list()
  result = reverse(head)
  print("Nodes of reversed LinkedList are: ", end='')
  result.print_list()


main()