Contoh menunjukkan cara golang melaksanakan pembalikan senarai terpaut

Penyongsangan senarai terpaut ialah masalah algoritma klasik dan titik pengetahuan yang sangat penting dalam struktur data dan algoritma. Penyongsangan senarai terpaut boleh digunakan secara meluas dalam amalan dan temu bual, jadi amat perlu bagi pengaturcara untuk menguasai algoritma penyongsangan senarai terpaut.

Adalah sangat mudah untuk melaksanakan algoritma pembalikan senarai terpaut dalam bahasa Go Di bawah kami akan menunjukkan cara melaksanakan algoritma pembalikan senarai terpaut.

1. Asas senarai terpaut

Pertama sekali, mari kita perkenalkan secara ringkas pengetahuan asas senarai terpaut. Senarai terpaut ialah struktur data bukan linear yang terdiri daripada berbilang nod. Setiap nod mempunyai dua sifat: satu yang menyimpan nilai elemen data, dan satu lagi yang merupakan penunjuk ke nod seterusnya.

Senarai terpaut mempunyai banyak kelebihan berbanding tatasusunan Contohnya, elemen boleh ditambah atau dipadamkan secara dinamik tanpa mengetahui bilangan elemen yang disimpan dalam senarai terpaut terlebih dahulu.

Nod senarai terpaut ringkas boleh ditakrifkan sebagai:

type ListNode struct {
    Val  int
    Next *ListNode
}

Dalam takrifan ini, Val ialah nilai yang disimpan dalam nod ini dan Next ialah penunjuk ke seterusnya nod . Jika nod ini adalah yang terakhir dalam senarai terpaut, Next tuding ke nil.

Nod kepala senarai terpaut mewakili permulaan senarai terpaut, selalunya juga dipanggil "nod sentinel" atau "nod maya". Ia tidak menyimpan sebarang nilai, hanya menunjuk ke nod sebenar yang pertama.

2. Algoritma pembalikan senarai terpaut

Sekarang kita mula menerangkan pelaksanaan algoritma pembalikan senarai terpaut. Idea asas algoritma pembalikan senarai terpaut adalah untuk melintasi keseluruhan senarai terpaut, membalikkan arah penunjuk setiap nod, dan akhirnya menghalakan nod kepala ke nod ekor senarai terpaut asal untuk melengkapkan pembalikan keseluruhan senarai terpaut.

Proses utama algoritma pembalikan senarai terpaut ialah pembalikan penunjuk bagi setiap nod Pelaksanaan khusus adalah seperti berikut:

// 将链表反转
func reverseList(head *ListNode) *ListNode {
    var prev, cur *ListNode
    cur = head
    for cur != nil {
        cur.Next, prev, cur = prev, cur, cur.Next
    }
    return prev
}

Inti algoritma ini adalah untuk menentukan dua. penunjuk prev dan cur, masing-masing mewakili nod sebelumnya dan nod semasa. Lintas keseluruhan senarai terpaut bermula dari nod kepala, bertukar-tukar mata bagi prev dan cur penunjuk setiap kali, sambil membiarkan cur menghala ke nod seterusnya.

3. Ujian

Akhir sekali, kami boleh mengesahkan bahawa kod kami adalah betul melalui beberapa kes ujian.

func main() {
    // 初始化一个链表
    n1 := &ListNode{Val: 1}
    n2 := &ListNode{Val: 2}
    n3 := &ListNode{Val: 3}
    n4 := &ListNode{Val: 4}
    n1.Next = n2
    n2.Next = n3
    n3.Next = n4
    // 打印原链表
    printList(n1)
    // 反转链表
    newHead := reverseList(n1)
    // 打印反转后的链表
    printList(newHead)
}

// 打印链表
func printList(head *ListNode) {
    p := head
    for p != nil {
        fmt.Printf("%d -> ", p.Val)
        p = p.Next
    }
    fmt.Println("nil")
}

Output:

1 -> 2 -> 3 -> 4 -> nil
4 -> 3 -> 2 -> 1 -> nil

4. Ringkasan

Pembalikan senarai terpaut ialah masalah algoritma yang sangat klasik bahasa Bagaimana untuk melaksanakan algoritma penyongsangan senarai terpaut. Dengan mempelajari algoritma ini, kami terus menyatukan dan memperdalam pemahaman kami tentang senarai terpaut dan petunjuk.

Atas ialah kandungan terperinci Contoh menunjukkan cara golang melaksanakan pembalikan senarai terpaut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!