Gymnastique algorithmique 24 Milieu de la liste liée

Middle of the LinkedList Ecrivez une méthode qui renvoie un nœud intermédiaire dans une LinkedList, en spécifiant le début d'une seule liste liée. Si le nombre total de nœuds dans LinkedList est pair, renvoie le deuxième nœud intermédiaire.

Exemple

Input: 1 -> 2 -> 3 -> 4 -> 5 -> null Output: 3

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null Output: 4

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null Output: 4

Solution L'une des stratégies de force brute consiste à compter d'abord le nombre de nœuds dans la LinkedList, puis à trouver le nœud central dans la deuxième itération. Il est important de pouvoir le faire en une seule itération.

Utilisez les méthodes de pointeur rapide et lent pour vous assurer que le pointeur rapide est toujours deux fois le nœud devant le pointeur lent. Ainsi, lorsque le pointeur rapide atteint la fin de la LinkedList, le pointeur lent pointe vers le nœud central.

la mise en oeuvre

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


def find_middle_of_linked_list(head):
  # Time Complexity O(N)
  # Space Complexity O(1)
  slow = head
  fast = head
  while (fast is not None and fast.next is not None):
    slow = slow.next
    fast = fast.next.next
  return slow


def main():
  head = Node(1)
  head.next = Node(2)
  head.next.next = Node(3)
  head.next.next.next = Node(4)
  head.next.next.next.next = Node(5)

  print("Middle Node: " + str(find_middle_of_linked_list(head).value))

  head.next.next.next.next.next = Node(6)
  print("Middle Node: " + str(find_middle_of_linked_list(head).value))

  head.next.next.next.next.next.next = Node(7)
  print("Middle Node: " + str(find_middle_of_linked_list(head).value))


main()

Recommended Posts

Gymnastique algorithmique 24 Milieu de la liste liée
Gymnastique algorithmique 24 Inverser une liste liée
À propos de la liste de base des bases de Python
Gymnastique algorithmique 12
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
Obtenez la liste des colonnes et la liste des données de CASTable
Obtenez la valeur de la couche intermédiaire de NN
[python] Vérifier les éléments de la liste tous, tous
Gymnastique algorithmique 24 sous-ensembles
Copiez la liste en Python
J'ai vérifié la liste des touches de raccourci de Jupyter
[Algorithm x Python] Comment utiliser la liste
Rechercher par la valeur de l'instance dans la liste
Visualisez le comportement de l'algorithme de tri avec matplotlib
[python] Récupère la liste des classes définies dans le module
Prenez note de la liste des utilisations de base de Pandas
Au milieu du développement, nous présenterons Alembic
Lire la liste de liens au format csv avec l'outil graphique
[Python] Obtenir la liste des noms ExifTags de la bibliothèque Pillow
Implémentation de l'algorithme "Algorithm Picture Book" en Python3 (Heap Sort Edition)
[Python] Affiche toutes les combinaisons d'éléments de la liste
[Maya Python] Écraser le contenu du script 2 ~ list Notes
J'ai étudié l'algorithme d'apprentissage de renforcement du trading d'algorithmes
Liste des modules python
Le début de cif2cell
Gymnastique algorithmique 23 Intervalles de fusion
Gymnastique d'algorithme 20 Supprimer les doublons
Algorithme Gymnastique 21 Cycle LinkedList
Le sens de soi
le zen de Python
Liste des fonctions d'activation (2020)
L'histoire de sys.path.append ()
Algorithme Gymnastique 24 Tri cyclique
Profondeur de la liste imbriquée
Affichage des fractions (liste)
Gymnastique d'algorithme 19 Sous-chaîne sans répétition
La vengeance des types: la vengeance des types
Essayez d'obtenir la liste des fonctions du paquet Python> os
[Maya Python] Écraser le contenu du script 3 ~ Liste des plugins inconnus
Maintenance de l'environnement de développement Django + MongoDB (en cours d'écriture)
Grattage du fichier Excel de la liste des magasins gérant des coupons communs régionaux
Implémentation de l'algorithme de "Algorithm Picture Book" en Python3 (Bubble Sort)
Obtenez le nombre d'éléments spécifiques dans la liste python
J'ai essayé d'implémenter l'algorithme FloodFill avec TRON BATTLE de CodinGame
Obtenez le nombre d'occurrences pour chaque élément de la liste
Itérateur qui peut balayer vers l'avant à partir du milieu de la séquence
Extraire la valeur de dict ou list sous forme de chaîne de caractères
Implémentation de l'algorithme «Algorithm Picture Book» en Python3 (tri sélectif)