Inverser une liste chaînée en un clin d'œil

C'est une question préférée à poser aux nouveaux développeurs. Assez simple si vous avez eu un cours décent sur les structures de données.

Inversez une seule liste chaînée. (Voici le Leetcode 206)

Pour l'implémentation, j'ai choisi de faire de la liste chaînée un type générique.

type Node[T any] struct {
    Data T
    Next *Node[T]
}

type LinkedList[T any] struct {
    Head *Node[T]
}

func (ll *LinkedList[T]) Append(data T) {
    newNode := &Node[T]{Data: data, Next: nil}

    if ll.Head == nil {
        ll.Head = newNode
        return
    }

    current := ll.Head
    for current.Next != nil {
        current = current.Next
    }
    current.Next = newNode
}

Et pour la fonction inverse, cela se fait en un seul passage en reconnaissant que tout ce que nous avons à faire est de maintenir un pointeur vers le nœud précédent, puis de définir le « suivant » d'un nœud donné sur le précédent.

Lorsque nous atteignons la fin, nous savons que le nœud actuel est la nouvelle « tête » de la liste.

func (ll *LinkedList[T]) ReverseLinkedList() {
    var prev *Node[T] = nil
    var ptr *Node[T] = ll.Head
    for ptr != nil {
        var next *Node[T] = ptr.Next
        ptr.Next = prev
        prev = ptr
        if next == nil {
            ll.Head = ptr
        }
        ptr = next
    }
}

Avons-nous manqué une condition aux limites ? Quelles complications s’ajoutent si la liste est désormais une liste doublement chaînée ? Faites-le-moi savoir dans les commentaires.

Merci !

Le code de cet article et de tous les articles de cette série peut être trouvé ici

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!