ホームページ > バックエンド開発 > Golang > Go でリンクされたリストを反転する

Go でリンクされたリストを反転する

WBOY
リリース: 2024-07-18 08:33:29
オリジナル
1130 人が閲覧しました

Reverse a linked list in go

これは、新しい開発者によく聞かれる質問です。まともなデータ構造クラスを持っていれば、非常に簡単です。

単一のリンクされたリストを反転します。 (これはリートコード 206)

実装のために、リンク リストをジェネリック型にすることを選択しました。

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
}
ログイン後にコピー

そして、リバース関数については、前のノードへのポインタを維持し、指定されたノードの「次」を前のノードに設定するだけであることを認識することで、シングルパスで実行されます。

最後に到達すると、現在のノードがリストの新しい「先頭」であることがわかります。

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
    }
}
ログイン後にコピー

境界条件を見逃していませんか?リストが二重リンクリストになった場合、どのような複雑さが追加されますか?コメント欄でお知らせください。

ありがとうございます!

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

以上がGo でリンクされたリストを反転するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

ソース:dev.to
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート