Kehren Sie eine verknüpfte Liste in go um

Dies ist eine Lieblingsfrage für 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 umgekehrte Funktion 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“ Knoten 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!

Den Code für diesen Beitrag und alle Beiträge dieser Reihe finden Sie hier

Das obige ist der detaillierte Inhalt vonKehren Sie eine verknüpfte Liste in go um. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!