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!