Bagaimana untuk membalikkan senarai pautan dalam golang

Menterbalikkan senarai terpaut ialah soalan biasa dan sering disebut dalam temu bual pengaturcaraan. Ia adalah masalah algoritma klasik yang digunakan secara meluas dan boleh digunakan untuk membalikkan susunan senarai terpaut dengan cepat. Artikel ini akan memperkenalkan algoritma dan langkah untuk melaksanakan senarai terpaut terbalik menggunakan bahasa golang.

1. Tentukan nod senarai terpaut tunggal

Sebelum kita mula melaksanakan senarai pautan terbalik, kita perlu mentakrifkan nod senarai pautan tunggal terlebih dahulu. Nod mengandungi dua bahagian yang sangat penting: medan data dan medan penunjuk. Medan data digunakan untuk menyimpan nilai nod, dan medan penunjuk digunakan untuk menunjuk ke nod seterusnya.

Dalam golang, kita boleh menggunakan struktur struct untuk mentakrifkan nod senarai terpaut tunggal. Struktur mengandungi dua atribut: Val, digunakan untuk mewakili nilai nod semasa, dan Seterusnya, digunakan untuk mewakili penunjuk ke nod seterusnya.

taip struct ListNode {

Val  int
Next *ListNode

}

2. Penyongsangan senarai pautan tunggal

Sekarang kami telah menentukan senarai pautan tunggal nod, langkah seterusnya ialah melaksanakan algoritma untuk menyongsangkan senarai terpaut. Kunci untuk membalikkan senarai terpaut adalah untuk melintasi senarai terpaut dan menukar penuding ke setiap nod.

Kita boleh melintasi setiap nod dalam senarai terpaut dari awal, dan menukar penunjuk "Seterusnya" mereka secara bergilir-gilir untuk menghala ke nod sebelumnya. Dengan cara ini, senarai terpaut boleh diterbalikkan.

Langkah algoritma untuk membalikkan senarai terpaut adalah seperti berikut:

(1) Tentukan dua penunjuk: pra dan cur, masing-masing menunjuk ke nod pertama dan nod kedua. pra ialah nod sebelumnya dan cur ialah nod semasa.

(2) Lintas senarai terpaut dan halakan penuding Seterusnya nod semasa ke pra nod sebelumnya.

(3) Gerakkan penuding ke belakang, tunjuk pra ke nod semasa dan lencong ke nod seterusnya.

(4) Ulang langkah 2 dan 3 sehingga keseluruhan senarai terpaut dilalui.

Kod pelaksanaan adalah seperti berikut:

func reverseLinkedList(kepala ListNode) ListNode {

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

}

3. Kod Ujian Songsang untuk senarai pautan terbalik

Untuk mengesahkan ketepatan senarai pautan terbalik, kami menulis beberapa kod ujian untuk dilaksanakan.

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. Terbalikkan senarai terpaut separa

Kecuali untuk terbalik Selain membalikkan keseluruhan senarai terpaut, kami juga boleh membalikkan sebahagian daripada senarai terpaut. Sebagai contoh, terbalikkan bahagian daripada nod m kepada nod n dalam senarai terpaut. Kami hanya perlu membuat sedikit pengubahsuaian berdasarkan membalikkan keseluruhan senarai terpaut.

Kita boleh mula-mula melintasi ke nod m-1, penunjuk pra menghala ke nod ini, dan melencong menghala ke nod ke-m. Kemudian, kami melakukan langkah membalikkan senarai terpaut sehingga kami berbalik ke nod ke-n.

Kod pelaksanaan adalah seperti berikut:

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. Kod ujian untuk membalikkan senarai terpaut separa

Untuk mengesahkan ketepatan membalikkan senarai terpaut separa, kami menulis beberapa kod ujian untuk pengesahan.

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. Ringkasan

Dalam artikel ini, kami Gunakan golang untuk melaksanakan algoritma senarai terpaut terbalik, termasuk membalikkan keseluruhan senarai terpaut dan membalikkan bahagian senarai terpaut. Membalikkan senarai terpaut ialah soalan temu bual biasa dan juga merupakan algoritma asas untuk menyelesaikan masalah yang berkaitan dengan senarai terpaut. Jika anda berminat dengan algoritma senarai terpaut, anda disyorkan supaya mengkaji secara mendalam algoritma berkaitan senarai terpaut lain, seperti penunjuk cepat dan perlahan, senarai terpaut bulat, memadamkan nod, dsb.

Atas ialah kandungan terperinci Bagaimana untuk membalikkan senarai pautan dalam golang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!