golangの単一リンクリストの反転

序文

コンピュータ サイエンスにおけるリンク リストは、ポインタを介して相互にリンクされた一連のノードで構成される基本的なデータ構造です。リンク リストでは、挿入操作と削除操作を簡単に実装できますが、要素を見つけるために走査が必要なため、アクセス操作のパフォーマンスは比較的低くなります。この記事では、Golang を使用して単連結リストの反転アルゴリズムを実装する方法を紹介します。

単一リンクリストの定義

Golang では、構造体を使用して単一リンクリストを定義できます。単一リンクリストのノードを表す構造体 Node を定義します。これには、ノードの値 val と、次のノードの位置を指すポインタ next が含まれます。

type Node struct {
    val  int
    next *Node
}

リンク リストの先頭ノードを指す先頭ポインターを定義します。リンクされたリストが空の場合、head は nil を指します。

var head *Node = nil

単一リンクリストの初期化

Golang では、新しい関数を使用してノードのメモリを割り当て、ノードのポインタを返すことができます。

func newNode(val int) *Node {
    return &Node{
        val,
        nil,
    }
}

単一リンク リストの作成は、newNode を使用してノードを継続的に追加することで実現できます。リンク リスト 1、2、および 3 を例にとると、コードは次のとおりです。

node1 := newNode(1)
node2 := newNode(2)
node3 := newNode(3)
  
node1.next = node2
node2.next = node3
head = node1

単一リンク リストの反転

単一リンク リストの反転を実現するには 2 つの方法があります。リスト: 反復と再帰。

メソッド 1: 反復

反復メソッドの中心となるアイデアは、リンクされたリストを走査し、現在のノードのポインターを前のノードにポイントして反転の目的を達成することです。

具体的な実装プロセスは次のとおりです。

• 3 つのポインタを定義します: prev、head、next
• リンクされたリストをたどって、head の次のポインタをポイントします。 prev
• prev ポインタを head にポイントします
• head を next にポイントします
• head が空になるまで上記の手順を繰り返します

Golang 実装コード

func reverseList1(head *Node) *Node {
    var prev *Node = nil
    var next *Node = nil
  
    for head != nil {
        next = head.next
        head.next = prev
        prev = head
        head = next
    }
  
    return prev
}

方法 2: 再帰

再帰的方法の核心的な考え方は、まずリンク リストの最後まで再帰し、次に走査されたノードに戻ることです。逆の順序。

具体的な実装プロセスは次のとおりです。

• リンクされたリストの最後まで再帰します
• ノードの次のノードを最後から 2 番目のノードにポイントします
• 最後から 2 番目のノードを配置します。2 つのノードの次のポイントは null を指します。
• 元のリンク リストのヘッド ノードが返されるまで、上記の手順を繰り返します。

Golang実装コードは次のとおりです:

func reverseList2(head *Node) *Node {
    if head == nil || head.next == nil {
        return head
    }
  
    newHead := reverseList2(head.next)
    head.next.next = head
    head.next = nil
  
    return newHead
}

完全なコードは次のとおりです:

package main
  
import (
    "fmt"
)
  
type Node struct {
    val  int
    next *Node
}
  
func newNode(val int) *Node {
    return &Node{
        val,
        nil,
    }
}
  
var head *Node
  
func reverseList1(head *Node) *Node {
    var prev *Node = nil
    var next *Node = nil
  
    for head != nil {
        next = head.next
        head.next = prev
        prev = head
        head = next
    }
  
    return prev
}
  
func reverseList2(head *Node) *Node {
    if head == nil || head.next == nil {
        return head
    }
  
    newHead := reverseList2(head.next)
    head.next.next = head
    head.next = nil
  
    return newHead
}
  
func main() {
    node1 := newNode(1)
    node2 := newNode(2)
    node3 := newNode(3)
  
    node1.next = node2
    node2.next = node3
  
    head = node1
  
    fmt.Println("原链表：")
    for head != nil {
        fmt.Printf("%d->", head.val)
        head = head.next
    }
  
    head = node1
    head = reverseList1(head)
  
    fmt.Println("
迭代法倒转后的链表：")
    for head != nil {
        fmt.Printf("%d->", head.val)
        head = head.next
    }
  
    head = node1
    head = reverseList2(head)
  
    fmt.Println("
递归法倒转后的链表：")
    for head != nil {
        fmt.Printf("%d->", head.val)
        head = head.next
    }
}

実行結果は次のとおりです:

原链表：
1->2->3->
迭代法倒转后的链表：
3->2->1->
递归法倒转后的链表：
3->2->1->

結論

この記事Golang を使用して単一リンク リストの反転を実装する方法を紹介し、反復と再帰という 2 つの異なる実装方法を紹介します。この記事を学習することで、誰もがこれら 2 つの手法の中核となる考え方を習得し、実際の開発に柔軟に適用できるようになると思います。

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