Senarai terbalik golang

Menterbalikkan senarai terpaut ialah masalah algoritma struktur data klasik, yang memerlukan nod pengendalian pada senarai terpaut, membalikkan senarai terpaut dan mengembalikan nod kepala terbalik.

Menggunakan bahasa golang untuk melaksanakan senarai terpaut terbalik boleh menunjukkan ciri operasi berorientasikan objek dan penuding golang. Mari kita terangkan secara terperinci cara melaksanakan senarai terpaut terbalik.

1. Tentukan struktur nod senarai terpaut

Pertama, kita perlu mentakrifkan struktur nod senarai terpaut, yang mengandungi dua pembolehubah ahli: nilai dan penunjuk ke nod seterusnya.

type ListNode struct {
    Val int
    Next *ListNode
}

2. Balikkan senarai terpaut

Seterusnya, kita perlu menulis fungsi untuk membalikkan senarai terpaut. Fungsi ini akan melintasi senarai terpaut dan membalikkan penunjuk seterusnya setiap nod ke nod sebelumnya, dan akhirnya mengembalikan nod kepala terbalik.

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    for head != nil {
        temp := head.Next
        head.Next = prev
        prev = head
        head = temp
    }
    return prev
}

Fungsi ini mengandungi penunjuk prev, yang digunakan untuk mengekalkan nod sebelumnya semasa proses traversal.

Pertama, kami memulakan penuding sebelumnya kepada null, menunjukkan bahawa ia terletak sebelum nod pertama senarai terpaut.

Kemudian kami mula merentasi senarai terpaut.

Dalam setiap gelung, kami menggunakan suhu penuding tambahan untuk menyimpan sementara nod seterusnya nod semasa.

Seterusnya, kami membalikkan penuding seterusnya bagi nod semasa kepada penuding sebelumnya, dan memasukkan nod semasa ke dalam kedudukan yang ditunjukkan oleh penuding sebelumnya.

Akhir sekali, kami menghalakan nod semasa ke temp supaya kami boleh melintasinya dalam gelung seterusnya.

3. Uji senarai terpaut terbalik

Melalui kod di atas, kami telah menyelesaikan pelaksanaan senarai terpaut terbalik. Seterusnya, kami boleh menulis beberapa kod ujian untuk mengesahkan sama ada fungsi senarai pautan terbalik kami adalah betul.

func main() {
    head := &ListNode{Val: 1}
    head.Next = &ListNode{Val: 2}
    head.Next.Next = &ListNode{Val: 3}
    head.Next.Next.Next = &ListNode{Val: 4}
    head.Next.Next.Next.Next = &ListNode{Val: 5}
    fmt.Println("Original List: ")
    printList(head)
    reversedList := reverseList(head)
    fmt.Println("Reversed List: ")
    printList(reversedList)
}

func printList(head *ListNode) {
    for head != nil {
        fmt.Printf("%d ", head.Val)
        head = head.Next
    }
    fmt.Println()
}

Dalam fungsi ujian ini, kami mula-mula membuat senarai terpaut dengan 5 nod dan mencetak tertib awal senarai terpaut Kemudian kami memanggil fungsi reverseList() untuk membalikkan senarai terpaut dan mengeluarkan terbalik senarai pautan terakhir. Pada akhirnya, kami mentakrifkan fungsi printList() untuk mencetak senarai terpaut.

Menjalankan fungsi ujian di atas, kita boleh mendapatkan keputusan berikut:

Original List: 
1 2 3 4 5 
Reversed List: 
5 4 3 2 1 

Seperti yang dapat dilihat daripada keputusan, kami berjaya membalikkan senarai terpaut.

Ringkasan

Menterbalikkan senarai terpaut ialah masalah algoritma yang sangat menarik dan biasa dan sering digunakan dalam aplikasi praktikal.

Melalui artikel ini, kami mempelajari cara melaksanakan senarai terpaut terbalik pada golang dan menggunakan ciri operasi berorientasikan objek dan penunjuk golang.

Dengan melaksanakan sendiri algoritma ini, kami dapat memahami dengan lebih baik struktur data senarai terpaut, dan pada masa yang sama memperdalam lagi penguasaan kami dalam bahasa golang.

Atas ialah kandungan terperinci Senarai terbalik golang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!