penyongsangan senarai terpaut tunggal golang

Kata Pengantar

Dalam sains komputer, senarai terpaut ialah struktur data asas yang terdiri daripada satu siri nod yang dipautkan antara satu sama lain melalui penunjuk. Senarai terpaut boleh melaksanakan operasi sisipan dan pemadaman dengan mudah, tetapi prestasi operasi capaian agak lemah kerana traversal diperlukan untuk mencari elemen. Artikel ini akan memperkenalkan cara menggunakan Golang untuk melaksanakan algoritma penyongsangan senarai terpaut tunggal.

Takrif senarai pautan tunggal

Di Golang, kita boleh menggunakan struktur untuk menentukan senarai pautan tunggal. Takrifkan struktur Nod, yang mewakili nod senarai terpaut tunggal, yang mengandungi nilai val nod dan penudingnya seterusnya menghala ke kedudukan nod seterusnya.

type Node struct { val int next *Node }

Tentukan penunjuk kepala, menunjuk ke nod kepala senarai terpaut. Jika senarai terpaut kosong, kepala menunjuk ke nil.

var head *Node = nil

Permulaan senarai terpaut tunggal

Di Golang, kita boleh menggunakan fungsi baharu untuk memperuntukkan memori nod dan mengembalikan penuding nod.

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

Buat senarai pautan tunggal, yang boleh dicapai dengan menambah nod secara berterusan menggunakan newNode. Mengambil senarai terpaut 1, 2, dan 3 sebagai contoh, kodnya adalah seperti berikut:

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

Penyongsangan senarai pautan tunggal

Terdapat dua kaedah untuk mencapai penyongsangan pautan tunggal senarai: lelaran dan rekursi.

Kaedah 1: Lelaran

Idea teras kaedah lelaran adalah untuk melintasi senarai terpaut dan menghalakan penuding nod semasa ke nod sebelumnya untuk mencapai tujuan pembalikan.

Proses pelaksanaan khusus adalah seperti berikut:

• Tentukan tiga petunjuk: sebelum, kepala, seterusnya
• Lintas senarai terpaut dan arahkan penuding kepala seterusnya ke prev
• Halakan penunjuk sebelumnya ke kepala
• Tuding kepala ke seterusnya
• Ulang langkah di atas sehingga kepala kosong

Kod pelaksanaan Golang adalah seperti berikut:

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 }

Kaedah 2: Rekursif

Idea teras kaedah rekursif adalah untuk mengulang ke penghujung senarai terpaut dahulu, dan kemudian kembali ke nod yang dilalui dalam susunan terbalik.

Proses pelaksanaan khusus adalah seperti berikut:

• Ulang ke penghujung senarai terpaut
• Tuding nod seterusnya nod ini ke nod kedua terakhir
• Letakkan nod kedua terakhir Titik seterusnya bagi dua nod menghala ke nol
• Ulang langkah di atas sehingga nod kepala senarai terpaut asal dikembalikan

Golang kod pelaksanaan adalah seperti berikut:

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 }

Kod lengkap adalah seperti berikut:

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 } }

Keputusan yang dijalankan adalah seperti berikut:

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

Kesimpulan

Artikel ini memperkenalkan cara menggunakan Golang untuk melaksanakan penyongsangan senarai terpaut tunggal, dan memperkenalkan dua kaedah pelaksanaan berbeza: lelaran dan rekursi . Saya percaya bahawa melalui kajian artikel ini, semua orang telah menguasai idea teras kedua-dua kaedah ini dan boleh menggunakannya secara fleksibel untuk pembangunan sebenar.

Atas ialah kandungan terperinci penyongsangan senarai terpaut tunggal golang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!