golangのリンクリストの反転

Golang は現在最も人気のあるプログラミング言語の 1 つであり、そのシンプルさと効率性が開発者に深く愛されています。 Golang では、リンク リストがさまざまなデータ構造で広く使用されています。ただし、リンク リストの操作は比較的複雑であるため、ポインター操作の正確さには特別な注意を払う必要があります。この記事では、Golang を使用してリンク リストを反転する方法について説明します。

リンクリストとは何ですか?

コンピュータ サイエンスでは、リンク リストはノードの集合であるデータ構造です。各ノードにはデータと次のノードへのポインタが含まれています。その特徴は、ノードの挿入と削除を効率的に実行できることですが、ノードにランダムにアクセスするにはリンク リスト全体を走査する必要があります。

リンク リストのデータ構造は次のとおりです。

type Node struct {
    data int
    next *Node
}

ここで、data はノードに格納されているデータ、next はノードに格納されているデータです。次のノードへのポインタ。 next が nil に等しい場合、これがリンク リストの最後のノードであることを意味します。

リンク リストの走査および挿入操作

リンク リストを走査する基本的な操作は、リンク リストの先頭ノードからリンク リストの末尾ノードまで走査することです。トラバーサル プロセス中に、ノードの値の出力など、特定の操作を各ノードで実行できます。以下は、リンク リストをトラバースする例です。

func printList(head *Node) {
    p := head
    for p != nil {
        fmt.Print(p.data, " ")
        p = p.next
    }
}

挿入操作では、まず挿入する位置を見つけてから、ポインターの指す位置を変更する必要があります。たとえば、リンク リストの 3 番目のノードの後に​​新しいノードを挿入すると、コードは次のようになります。

func insert(head *Node, pos int, value int) *Node {
    p := head
    for i := 1; i < pos && p != nil; i++ {
        p = p.next
    }
    if p == nil {
        return head
    }
    newNode := &Node{data: value}
    newNode.next = p.next
    p.next = newNode
    return head
}

リンク リストの反転

リンク リストの反転とは、次の順序を逆にすることを意味します。リンクされたリスト内のノード、つまり元のノード。最初のノードが最後のノードになり、元の最後のノードが最初のノードになります。リンク リストを反転するプロセスには、リンク リスト内のノード間のポインタを反転することが含まれます。以下は、リンク リストを反転するための実装コードです:

func reverseList(head *Node) *Node {
    if head == nil || head.next == nil {
        return head
    }
    var prev *Node
    curr := head
    for curr != nil {
        next := curr.next
        curr.next = prev
        prev = curr
        curr = next
    }
    return prev
}

まず、リンク リストが空であるか、ノードが 1 つしかないかを判断します。この場合、リンク リストを反転する必要はなく、元のリンク リストはリストの先頭ノードが直接返されます。次に、2 つのポインターを定義します。prev は現在のノードの前のノードを指し、curr は現在のノードを指します。ヘッド ノードから開始してリンク リストを走査し、各ループは現在のノードの next ポインタを前のノードにポイントし、その後 prev と curr## を移動します。 # リンクされたリスト全体が走査されるまで、1 つ前のノードを後方にポインタします。最後に、反転されたリストの先頭ノードが返されます。

テスト コードは次のとおりです:

func main() {
    head := &Node{data: 1}
    head.next = &Node{data: 2}
    head.next.next = &Node{data: 3}
    head.next.next.next = &Node{data: 4}
    fmt.Println("Original list:")
    printList(head)
    head = reverseList(head)
    fmt.Println("
Reversed list:")
    printList(head)
}

出力結果は次のとおりです:

Original list:
1 2 3 4
Reversed list:
4 3 2 1

概要

この記事では、Golang のリンク リストの基本操作を紹介します。リンクされたリストを逆にする方法も説明します。リンク リストの操作は少し複雑ですが、挿入と削除が効率的に行えるという利点があり、さまざまなシーンで広く使用されています。リンク リストを使用する場合は、メモリ リークなどの問題を避けるために、ポインタの正確さに特別な注意を払う必要があります。

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