例は、golang がリンク リストの反転を実装する方法を示しています

リンク リストの反転は古典的なアルゴリズムの問​​題であり、データ構造とアルゴリズムにおける非常に重要な知識ポイントです。リンク リスト逆変換は実務や面接で広く使用できるため、プログラマがリンク リスト逆変換アルゴリズムを習得することは非常に必要です。

Go 言語でリンク リスト反転アルゴリズムを実装することも非常に簡単です。以下では、リンク リスト反転アルゴリズムの実装方法を示します。

1. リンクリストの基礎

まずはリンクリストの基礎知識を簡単にご紹介します。リンク リストは、複数のノードで構成される非線形データ構造です。各ノードには 2 つのプロパティがあります。1 つはデータ要素の値を格納するプロパティ、もう 1 つは次のノードへのポインタです。

リンク リストには、配列に比べて多くの利点があります。たとえば、リンク リストに格納されている要素の数を事前に知らなくても、要素を動的に追加または削除できます。

単純なリンク リスト ノードは次のように定義できます:

type ListNode struct {
    Val  int
    Next *ListNode
}

この定義では、Val はこのノードに格納されている値であり、Next は次のノードへのポインタ。このノードがリンク リストの最後のノードである場合、Next は nil を指します。

リンク リストのヘッド ノードはリンク リストの先頭を表し、「センチネル ノード」または「仮想ノード」とも呼ばれます。値は格納されず、最初の実際のノードを指すだけです。

2. リンク リスト反転アルゴリズム

次に、リンク リスト反転アルゴリズムの実装について説明します。リンク リスト反転アルゴリズムの基本的な考え方は、リンク リスト全体を走査し、各ノードのポインタの方向を反転し、最後に元のリンク リストの先頭ノードを末尾ノードにポイントして、リンク リストの反転を完了することです。リンクされたリスト全体。

リンクリスト反転アルゴリズムの主要な処理は、各ノードのポインタの反転であり、具体的な実装方法は次のとおりです:

// 将链表反转
func reverseList(head *ListNode) *ListNode {
    var prev, cur *ListNode
    cur = head
    for cur != nil {
        cur.Next, prev, cur = prev, cur, cur.Next
    }
    return prev
}

このアルゴリズムの核心は、次の 2 つのノードの定義です。 pointersprev と cur はそれぞれ前のノードと現在のノードを表します。ヘッド ノードから開始してリンク リスト全体を走査し、毎回 prev と cur ポインターのポイントを交換しながら、cur が次のノードを指すようにします。

3. テスト

最後に、いくつかのテスト ケースを通じてコードが正しいかどうかを確認できます。

func main() {
    // 初始化一个链表
    n1 := &ListNode{Val: 1}
    n2 := &ListNode{Val: 2}
    n3 := &ListNode{Val: 3}
    n4 := &ListNode{Val: 4}
    n1.Next = n2
    n2.Next = n3
    n3.Next = n4
    // 打印原链表
    printList(n1)
    // 反转链表
    newHead := reverseList(n1)
    // 打印反转后的链表
    printList(newHead)
}

// 打印链表
func printList(head *ListNode) {
    p := head
    for p != nil {
        fmt.Printf("%d -> ", p.Val)
        p = p.Next
    }
    fmt.Println("nil")
}

出力:

1 -> 2 -> 3 -> 4 -> nil
4 -> 3 -> 2 -> 1 -> nil

4. 概要

リンク リストの反転は、非常に古典的なアルゴリズムの問​​題です。この記事では、Go でリンク リストを実装する方法を紹介します。言語 アルゴリズムを反転します。このアルゴリズムを学習することで、リンク リストとポインタについての理解をさらに強化し、深めることができます。

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