golangでリンクリストを逆にする方法

リンク リストの反転はよくある質問であり、プログラミングのインタビューでもよく取り上げられます。これは広く使用されている古典的なアルゴリズムの問​​題であり、リンク リストの順序をすばやく逆転するために使用できます。この記事では、golang言語を使用して逆リンクリストを実装するアルゴリズムと手順を紹介します。

1. 単一リンク リスト ノードの定義

逆リンク リストの実装を開始する前に、まず単一リンク リスト ノードを定義する必要があります。ノードには、データ フィールドとポインター フィールドという 2 つの非常に重要な部分が含まれています。データ フィールドはノードの値を格納するために使用され、ポインター フィールドは次のノードを指すために使用されます。

golang では、構造体構造を使用して、単一リンクされたリスト ノードを定義できます。この構造体には、現在のノードの値を表すために使用される Val と、次のノードへのポインターを表すために使用される Next の 2 つの属性が含まれています。

type ListNode struct {

Val  int
Next *ListNode

}

2. 単一リンク リストの反転

これで、単一リンク リストのノードを定義しました。次のステップは、リンク リストを反転するためのアルゴリズムを実装することです。リンク リストを反転する鍵は、リンク リストを走査し、各ノードへのポインタを変更することです。

リンクされたリスト内の各ノードを最初からたどって、その「次」ポインタを前のノードを指すように順番に変更できます。このようにして、リンクされたリストを逆にすることができます。

リンク リストを反転するアルゴリズムの手順は次のとおりです。

(1) 2 つのポインター、pre と cur を定義し、それぞれ最初のノードと 2 番目のノードを指します。 pre は前のノード、cur は現在のノードです。

(2) リンクされたリストを走査し、現在のノードの Next ポインタが前のノード pre を指すようにします。

(3) ポインタを後方に移動し、pre を現在のノードにポイントし、cur を次のノードにポイントします。

(4) リンクされたリスト全体を走査するまで、手順 2 と 3 を繰り返します。

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

func reverseLinkedList(head ListNode) ListNode {

var pre *ListNode
cur := head
for cur != nil {
    next := cur.Next
    cur.Next = pre
    pre = cur
    cur = next
}
return pre

}

3. 逆リンク リストのテスト コード

逆リンク リストの正確性を検証するために、実行するテスト コードを作成します。

func TestReverseLinkedList(t *testing.T) {

head := &ListNode{Val: 1}
node1 := &ListNode{Val: 2}
node2 := &ListNode{Val: 3}
node3 := &ListNode{Val: 4}
node4 := &ListNode{Val: 5}

head.Next = node1
node1.Next = node2
node2.Next = node3
node3.Next = node4

newHead := reverseLinkedList(head)

assert.Equal(t, newHead.Val, 5)
assert.Equal(t, newHead.Next.Val, 4)
assert.Equal(t, newHead.Next.Next.Val, 3)
assert.Equal(t, newHead.Next.Next.Next.Val, 2)
assert.Equal(t, newHead.Next.Next.Next.Next.Val, 1)

}

4. リンクされたリストの一部を反転します

さらに全体を反転する リンクされたリストに加えて、リンクされたリストの一部を反転することもできます。たとえば、リンクリストのノード m からノード n までの部分を反転します。リンクされたリスト全体を反転することに基づいてわずかな変更を加えるだけで済みます。

最初に m-1 番目のノードに移動し、pre ポインタはこのノードを指し、cur は m 番目のノードを指します。次に、n 番目のノードまで反転するまで、リンク リストを反転する手順を実行します。

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

func reverseBetween(head ListNode, m int, n int) ListNode {

dummy := &ListNode{0, head}
pre := dummy

for i := 1; i < m; i++ {
    pre = pre.Next
}

cur := pre.Next
for i := m; i < n; i++ {
    next := cur.Next
    cur.Next = next.Next
    next.Next = pre.Next
    pre.Next = next
}

return dummy.Next

}

5. 部分リンクリスト反転のテストコード

部分リンクリスト反転の正しさを検証するために、検証用のテストコードを書きます。

func TestReverseBetween(t *testing.T) {

head := &ListNode{Val: 1}
node1 := &ListNode{Val: 2}
node2 := &ListNode{Val: 3}
node3 := &ListNode{Val: 4}
node4 := &ListNode{Val: 5}

head.Next = node1
node1.Next = node2
node2.Next = node3
node3.Next = node4

newHead := reverseBetween(head, 2, 4)

assert.Equal(t, newHead.Val, 1)
assert.Equal(t, newHead.Next.Val, 4)
assert.Equal(t, newHead.Next.Next.Val, 3)
assert.Equal(t, newHead.Next.Next.Next.Val, 2)
assert.Equal(t, newHead.Next.Next.Next.Next.Val, 5)

}

6. 概要

この記事では golang を使用しますリンク リスト全体の反転およびリンク リストの一部の反転を含む、反転リンク リスト アルゴリズムを実装しました。リンク リストの反転は面接でよくある質問であり、リンク リストに関連する問題を解決するための基本的なアルゴリズムでもあります。リンク リスト アルゴリズムに興味がある場合は、高速ポインタとスロー ポインタ、循環リンク リスト、ノードの削除など、他のリンク リスト関連アルゴリズムを詳しく学習することをお勧めします。

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