在這篇文章中,我探索了另一種鍊錶演算法。這個有點難。
建立一個函數來刪除鍊錶末端的第 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中文網其他相關文章!