リンクされたリストの末尾から 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」後ろになります。これで、高速が終了するまで、両方のポインタをロックステップで移動できます。

その後、n 番目から最後までのノードを削除して、それを返すことができます。

もっと良い方法はありますか?コメント欄でお知らせください。

ありがとうございます!

この投稿とこのシリーズのすべての投稿のコードはここにあります

以上がリンクされたリストの末尾から N 番目を削除しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。