Dies ist eine beliebte Frage an neue Entwickler. Ziemlich einfach, wenn Sie einen anständigen Datenstrukturkurs hatten.

Eine einzelne verknüpfte Liste umkehren. (Dies ist Leetcode 206)

Für die Implementierung habe ich mich dafür entschieden, die verknüpfte Liste zu einem generischen Typ zu machen.

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
}

Und für die Umkehrfunktion wird dies in einem einzigen Durchgang erledigt, indem wir erkennen, dass alles, was wir tun müssen, ist, einen Zeiger auf den vorherigen Knoten beizubehalten und dann den „nächsten“ eines bestimmten Knotens auf den vorherigen zu setzen.

Wenn wir das Ende erreichen, wissen wir, dass der aktuelle Knoten der neue „Kopf“ der Liste ist.

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
    }
}

Haben wir eine Randbedingung übersehen? Welche Komplikationen kommen hinzu, wenn die Liste nun eine doppelt verknüpfte Liste ist? Lass es mich in den Kommentaren wissen.

Danke!

Der Code für diesen Beitrag und alle Beiträge dieser Serie finden Sie hier