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

Screen Shot 2020-08-07 at 21.27.40.png

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

Recommended Posts

Gymnastique algorithmique 24 Inverser une liste liée
Gymnastique algorithmique 24 Milieu de la liste liée
Gymnastique algorithmique 12
Gymnastique algorithmique 10
Gymnastique algorithmique 3
Gymnastique algorithmique 9
Gymnastique algorithmique 14
liste liée
Gymnastique algorithmique 2
Gymnastique algorithmique 7
Gymnastique algorithmique 15
Gymnastique algorithmique 16
Gymnastique algorithmique 8
Gymnastique algorithmique 17
Gymnastique algorithmique 18
Gymnastique algorithmique 11
Exercice d'algorithme 5
Gymnastique algorithmique 4
Gymnastique algorithmique 22 Mise au carré d'un tableau trié
Répertorier l'opération inverse
Algorithme A * (édition Python)
Gymnastique algorithmique 23 Intervalles de fusion
Gymnastique d'algorithme 20 Supprimer les doublons
Algorithme Gymnastique 21 Cycle LinkedList
Algorithme Gymnastique 24 Tri cyclique
Gymnastique d'algorithme 19 Sous-chaîne sans répétition
Soit Code Day78 à partir de zéro "206. Liste liée inversée"
Un commentaire sur l'algorithme de Boruta
La liste Python n'est pas une liste