Retourne le nœud du milieu de la liste liée avec récursivité

La raison pour laquelle cela imprime la bonne valeur mais la modification de l'impression en une instruction return ne fonctionne pas est que vous ne renvoyez pas le nœud dans votre cas de base. Ainsi, lorsque vous trouvez le point médian et renvoyez le nœud, le nœud précédent ne renvoie rien et n'utilise pas le résultat de l'étape récursive. Voici une modification qui utilisera le résultat de votre étape récursive et le renverra dans la chaîne d'appels.

Je ne suis pas entièrement convaincu que le calcul du point médian était correct dans tous les cas (le cas de 3 nœuds renverra le nœud 1 au lieu de node 2) donc je l'ai légèrement modifié.

def find_mid(self, node, ret_count, ):
    if node.next == None:
        self.len += 1
        return None
    else:
        self.len += 1
        # return_node will either be the midpoint if we have found it, or None if we are still searching
        return_node = self.find_mid(node.next, ret_count + 1)

        # We have found the midpoint no need to check ret_count anymore
        if return_node:
            return return_node

    # If we make it here we have not found the midpoint node but have counted the total number of Nodes.
    # Set midpoint assuming an even number of nodes
    midpoint = int(self.len/2)
    # If odd number of nodes set midpoint accordingly
    if self.len % 2 != 0:
        midpoint = int((self.len+1)/2)

    # Check if the current node is the midpoint (len = 3 or len = 4 results in node 2 being midpoint
    if ret_count == midpoint:
        # Return the node
        return node
    else:
        # Potentially not necessary but will ensure that non-midpoint recursive steps return None
        return None

La récursivité est un mauvais choix pour opérer sur des listes chaînées. Utilisez presque toujours une boucle, ce qui est simple à raisonner, a moins de surcharge et ne limite pas la taille de la liste à la pile d'appels. Il est plus facile d'accéder et de manipuler les éléments environnants de manière itérative.

Obtenir le milieu d'une liste chaînée est facile de manière itérative: gardez deux références à la tête, puis déplacez-en une deux fois plus vite que l'autre jusqu'à ce que la référence rapide atteigne la fin de la liste . Le pointeur lent pointera vers le nœud du milieu. La technique à deux pointeurs est l'un des outils fondamentaux pour travailler avec des listes chaînées.

def middle_node(fast, slow=None):
    if not slow:
        slow = fast

    if fast and fast.next:
        return middle_node(fast.next.next, slow.next)

    return slow

Vous pouvez le faire de manière récursive en utilisant exactement la même méthodologie: une référence rapide et une référence lente. Voici un exemple qui se branche dans le passe-partout ci-dessus:

from collections import namedtuple

def middle_node(fast):
    slow = fast

    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next

    return slow

if __name__ == "__main__":
    Node = namedtuple("Node", "val next")
    odd = Node(0, Node(1, Node(2, Node(3, Node(4, None)))))
    even = Node(0, Node(1, Node(2, Node(3, Node(4, Node(5, None))))))
    print(middle_node(odd).val) # => 2
    print(middle_node(even).val) # => 3

Pour les listes de longueur impaire avec deux éléments du milieu, ces méthodes renvoient toujours celle la plus proche de la queue, mais vous pouvez ajouter une vérification supplémentaire fast.next.next au cas de base ou une terminaison de boucle conditionnelle pour renvoyer l'élément central plus près de la tête si vous en avez besoin.

Vous pouvez voir les offres de la version récursive aucun avantage en termes de lisibilité ou d'élégance pour justifier les restrictions supplémentaires de frais généraux et de taille qu'il impose. La récursivité est mieux adaptée aux structures imbriquées non linéaires comme les arbres où les données sont larges (ce qui signifie que la pile d'appels est beaucoup plus capable de contenir les données sans débordement). La nature non linéaire des arbres rend très difficile l'utilisation d'une boucle et d'une pile explicite pour gérer certaines traversées typiques.

La récursivité est un excellent choix pour le traitement des listes chaînées car les listes chaînées sont des structures de données récursives. La récursivité permet à la structure de notre programme de correspondre à celle de la structure de nos données -

from linked_list import linked_list

t1 = linked_list.from_list([1, 2, 3])
t2 = linked_list.from_list([1, 2, 3, 4])
t3 = linked_list.from_list([1, 2, 3, 4, 5])

print(t1) # 1 -> 2 -> 3 -> None
print(t2) # 1 -> 2 -> 3 -> 4 -> None
print(t3) # 1 -> 2 -> 3 -> 4 -> 5 -> None

print(t1.middle()) # => 2
print(t2.middle()) # => 3
print(t3.middle()) # => 3

Obtenons une sortie de nos blocs de construction de base -

# linked_list.py

empty = # ...

class node # ...

def to_str # ...

def middle # ...

def from_list(l = []):
  if not l:
    return empty
  else:
    return node(l[0], from_list(l[1:]))

class linked_list:
  def __init__(self, root = None):
    self.root = root
  def __str__(self):
    return to_str(self.root)
  def middle(self):
    return middle(self.root)
  def from_list(l = []):
    return linked_list(from_list(l))

Wrapping le module fonctionnel dans une classe le rend plus pythonique -

# main.py

from linked_list import node, to_str, middle

t1 = node(1, node(2, node(3)))
t2 = node(1, node(2, node(3, node(4))))
t3 = node(1, node(2, node(3, node(4, node(5)))))

print(to_str(t1)) # 1 -> 2 -> 3 -> None
print(to_str(t2)) # 1 -> 2 -> 3 -> 4 -> None
print(to_str(t3)) # 1 -> 2 -> 3 -> 4 -> 5 -> None

print(middle(t1)) # => 2
print(middle(t2)) # => 3
print(middle(t3)) # => 3

Nous bénéficions maintenant de tous les avantages d'un module de style fonctionnel avec les commodités d'une interface de style oop -

# linked_list.py

empty = None

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

def to_str(t = empty):
  if not t:
    return "None"
  else:
    return f"{t.value} -> {to_str(t.next)}"

def middle(t = empty):
  def loop(t, ff):
    if not t:
      return None
    elif ff and ff.next:
      return loop(t.next, ff.next.next)
    else:
      return t.value
  return loop(t, t)