逆リンクリスト golang

リンク リストの反転は古典的なデータ構造アルゴリズムの問​​題であり、リンク リスト上のノードを操作し、リンク リストを反転して、反転したヘッド ノードを返す必要があります。

Golang 言語を使用して逆リンク リストを実装すると、golang のオブジェクト指向機能とポインタ操作機能を効果的に実証できます。逆リンク リストの実装方法を詳しく説明します。

1. リンク リスト ノード構造を定義する

まず、値と次のノードへのポインターという 2 つのメンバー変数を含むリンク リスト ノード構造を定義する必要があります。

type ListNode struct {
    Val int
    Next *ListNode
}

2. リンク リストを反転する

次に、リンク リストを反転する関数を作成する必要があります。この関数はリンク リストを走査し、各ノードの次のポインタを前のノードに反転し、最後に反転したヘッド ノードを返します。

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    for head != nil {
        temp := head.Next
        head.Next = prev
        prev = head
        head = temp
    }
    return prev
}

この関数には、トラバーサル プロセス中に前のノードを維持するために使用されるポインター prev が含まれています。

まず、prev ポインターを空に初期化し、リンク リストの最初のノードの前に位置することを示します。

次に、リンクされたリストの探索を開始します。

各ループでは、追加のポインター temp を使用して、現在のノードの次のノードを一時的に保存します。

次に、現在のノードの次のポインタを前のポインタに反転し、前のノードが指す位置に現在のノードを挿入します。

最後に、次のループでそれを走査できるように、現在のノードを temp にポイントします。

3. 逆リンク リストのテスト

上記のコードにより、逆リンク リストの実装が完了しました。次に、逆リンク リスト関数が正しいかどうかを検証するテスト コードを作成します。

func main() {
    head := &ListNode{Val: 1}
    head.Next = &ListNode{Val: 2}
    head.Next.Next = &ListNode{Val: 3}
    head.Next.Next.Next = &ListNode{Val: 4}
    head.Next.Next.Next.Next = &ListNode{Val: 5}
    fmt.Println("Original List: ")
    printList(head)
    reversedList := reverseList(head)
    fmt.Println("Reversed List: ")
    printList(reversedList)
}

func printList(head *ListNode) {
    for head != nil {
        fmt.Printf("%d ", head.Val)
        head = head.Next
    }
    fmt.Println()
}

このテスト関数では、まず 5 つのノードを持つリンク リストを作成し、リンク リストの初期順序を出力します。次に、reverseList() 関数を呼び出してリンク リストを反転し、その逆を出力します。最後のリンクされたリスト。最後に、リンクされたリストを印刷する printList() 関数を定義します。

上記のテスト関数を実行すると、次の結果が得られます:

Original List: 
1 2 3 4 5 
Reversed List: 
5 4 3 2 1 

結果からわかるように、リンク リストを正常に反転できました。

概要

リンク リストの反転は、非常に興味深い一般的なアルゴリズム問題であり、実際のアプリケーションでよく使用されます。

この記事を通じて、golang で逆リンク リストを実装する方法と、golang のオブジェクト指向機能とポインタ操作機能を使用する方法を学びました。

このアルゴリズムを自分で実装することで、リンク リストのデータ構造をより深く理解できると同時に、golang 言語の習得をさらに深めることができます。

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