Gymnastique algorithmique 24 Inverser une liste liée

Reverse a LinkedList Spécifier le début d'une seule LinkedList inverse la LinkedList. Ecrivez une fonction qui renvoie une nouvelle tête pour la LinkedList inversée.

Exemple

Solution Vous pouvez utiliser les trois pointeurs, précédent, actuel et suivant, pour inverser la LinkedList en une seule itération.

la mise en oeuvre

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