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 サイトの他の関連記事を参照してください。