刪除鍊錶末尾的第 N 個

在這篇文章中，我探索了另一種鍊錶演算法。這個有點難。

建立一個函數來刪除鍊錶末端的第 n 個節點。

這來自leetcode問題。與 leetcode 問題一樣，「n」是從 1 開始的，可以從 1 到列表的長度。

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
}

關鍵是使用雙指標。我們先初始化一個指向列表頭部的快指標和慢指標。

接下來，我們將快指標向前移動 n 個節點。這樣，慢指針現在位於快指針後面的“n”處。現在，我們可以以鎖步方式移動兩個指針，直到 fast 結束。

然後我們可以刪除倒數第 n 個節點並將其傳回。

有更好的方法嗎？請在評論中告訴我。

謝謝！

這篇文章以及本系列所有文章的程式碼可以在這裡找到

以上是刪除鍊錶末尾的第 N 個的詳細內容。更多資訊請關注PHP中文網其他相關文章！