C'est une question préférée à poser aux nouveaux développeurs. Assez simple si vous avez eu une classe de structures de données décente.

Inversez une seule liste chaînée. (Il s'agit du 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 devons 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 le nouveau « 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-moi savoir dans les commentaires.

Merci!

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