Entfernen Sie das N-te vom Ende der verknüpften Liste

In diesem Beitrag erkunde ich einen anderen Linked-List-Algorithmus. Dieser ist etwas schwieriger.

Erstellen Sie eine Funktion, um den n-ten Knoten vom Ende einer verknüpften Liste zu entfernen.

Dies ist auf ein Leetcode-Problem zurückzuführen. Wie beim Leetcode-Problem ist 'n' einsbasiert und kann von 1 bis zur Länge der Liste reichen.

func (ll *LinkedList[T]) RemoveNthFromEnd(n int) *Node[T] {
    if n == 0 {
        return nil
    }
    fast := ll.Head // this moves to the end
    slow := ll.Head // this should be one behind the nth from end

    for count := 0; count < n; count++ {
        if fast == nil { // list is too short
            return nil
        }
        fast = fast.Next
    }
    if fast == nil { // special case, removing head
        res := ll.Head
        ll.Head = ll.Head.Next
        return res
    }
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next
    }
    res := slow.Next
    slow.Next = slow.Next.Next
    return res
}

Der Schlüssel dazu ist die Verwendung von Doppelzeigern. Wir beginnen mit der Initialisierung eines schnellen und eines langsamen Zeigers auf den Kopf der Liste.

Als nächstes bewegen wir den schnellen Zeiger um n Knoten vorwärts. Auf diese Weise liegt der langsame Zeiger jetzt „n“ hinter dem schnellen Zeiger. Jetzt können wir beide Zeiger im Gleichschritt bewegen, bis fast am Ende ist.

Wir können dann den n-ten Knoten entfernen und ihn zurückgeben.

Gibt es einen besseren Weg? 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 vonEntfernen Sie das N-te vom Ende der verknüpften Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!