golangでリンクリストを逆にする方法
- PHPzオリジナル
- 2023-04-23 10:22:20837ブラウズ
リンク リストの反転はよくある質問であり、プログラミングのインタビューでもよく取り上げられます。これは広く使用されている古典的なアルゴリズムの問題であり、リンク リストの順序をすばやく逆転するために使用できます。この記事では、golang言語を使用して逆リンクリストを実装するアルゴリズムと手順を紹介します。
- 単一リンク リスト ノードの定義
逆リンク リストの実装を開始する前に、まず単一リンク リスト ノードを定義する必要があります。ノードには、データ フィールドとポインター フィールドという 2 つの非常に重要な部分が含まれています。データ フィールドはノードの値を格納するために使用され、ポインター フィールドは次のノードを指すために使用されます。
golang では、構造体構造を使用して、単一リンクされたリスト ノードを定義できます。この構造体には、現在のノードの値を表すために使用される Val と、次のノードへのポインターを表すために使用される Next の 2 つの属性が含まれています。
type ListNode struct {
Val int Next *ListNode
}
- 単一リンク リストの反転
これで、単一リンク リストのノードを定義しました。次のステップは、リンク リストを反転するためのアルゴリズムを実装することです。リンク リストを反転する鍵は、リンク リストを走査し、各ノードへのポインタを変更することです。
リンクされたリスト内の各ノードを最初からたどって、その「次」ポインタを前のノードを指すように順番に変更できます。このようにして、リンクされたリストを逆にすることができます。
リンク リストを反転するアルゴリズムの手順は次のとおりです。
(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
}
- 逆リンク リストのテスト コード
逆リンク リストの正確性を検証するために、実行するテスト コードを作成します。
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)
}
- リンクされたリストの一部を反転します
さらに全体を反転する リンクされたリストに加えて、リンクされたリストの一部を反転することもできます。たとえば、リンクリストのノード 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
}
- 部分リンクリスト反転のテストコード
部分リンクリスト反転の正しさを検証するために、検証用のテストコードを書きます。
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)
}
- 概要
この記事では golang を使用しますリンク リスト全体の反転およびリンク リストの一部の反転を含む、反転リンク リスト アルゴリズムを実装しました。リンク リストの反転は面接でよくある質問であり、リンク リストに関連する問題を解決するための基本的なアルゴリズムでもあります。リンク リスト アルゴリズムに興味がある場合は、高速ポインタとスロー ポインタ、循環リンク リスト、ノードの削除など、他のリンク リスト関連アルゴリズムを詳しく学習することをお勧めします。
以上がgolangでリンクリストを逆にする方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。