Senarai terpaut terbalik dalam satu baris

editor php Yuzai memperkenalkan anda kepada algoritma struktur data biasa - "Senarai pautan terbalik antara baris". Dalam algoritma ini, kita perlu membalikkan susunan nod dalam senarai terpaut. Melalui pelaksanaan kod yang ringkas dan cekap, kami boleh melengkapkan operasi ini dalam satu baris, membalikkan sepenuhnya susunan senarai terpaut. Algoritma ini sangat berguna dalam pengaturcaraan sebenar dan boleh memainkan peranan penting dalam kedua-dua pemprosesan data dan reka bentuk algoritma. Mari belajar tentang algoritma hebat ini bersama-sama!

Kandungan soalan

Saya baru sahaja menemui penyelesaian untuk senarai pautan terbalik menggunakan satu baris dalam go pada leetcode. Ia berfungsi, tetapi saya tidak faham bagaimana untuk melaksanakannya.

Itu sahaja:

func reverselist(head *listnode) (prev *listnode) {
    for head != nil {
        prev, head, head.next = head, head.next, prev 
    }
    
    return
}

Sebagai contoh, biarkan senarai itu [1->2->3->4->5->nil].

Saya tahu ia berfungsi seperti ini:

1. Laksanakan dahulu head.next = prev (head.next = nil, 所以现在 head = [1->nil])

2. Kemudian, prev = head （在这一步 prev = [1->nil] 就像上一步中的 head sama)

3. head = head.next 这就是魔法。对于第二步go中的prev，使用head = [1->nil]，但是在这一步之后head = [2->3->4->5->nil]

Jadi bila head != nil 时，它会进行迭代，并在第二步 prev = [2->1->nil] 、 head = [3->4->5->nil] dan seterusnya.

Baris ini boleh dinyatakan sebagai:

for head != nil {
        a := *head
        prev, a.Next = &a, prev
        head = head.Next
    }

Adakah saya betul? Mengapa ini berlaku?

Penyelesaian

Pembolehubah di sebelah kiri ungkapan akan diberikan kepada nilai di sebelah kanan ungkapan pada masa itu. Ini adalah penggunaan bahasa yang bijak.

Untuk memudahkan pemahaman, mari lihat contoh.

Tetapan

Berikut ialah senarai pautan kami: 1 -> 2 ->

Sebelum fungsi dilaksanakan,

Kepala ialah *nod 1
sebelumnya ialah sifar (tidak dimulakan)
kepala.seterusnya ialah *nod 2

Langkah demi langkah

prev, head, head.next = head, head.next, prev

Mari kita pecahkan,

sebelumnya (tiada) = kepala (*nod 1)
kepala (*Nod 1) = kepala.seterusnya (*Nod 2)
kepala.seterusnya (*nod 2) = sebelumnya (tiada)

Lelaran seterusnya,

sebelumnya (*nod 1) = kepala (*nod 2)
kepala (*nod 2) = kepala.seterusnya (*nod 3)
head.next (*nod 3) = sebelumnya (*nod 1)

Ringkasan

Pada asasnya, ia membalikkan

ke nod sebelumnya dan bergerak sebelum dan menuju ke nod seterusnya. head.next

Bandingkan ini dengan algoritma buku teks dalam pergi untuk menjelaskannya:

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode

    for head != nil {
        nextTemp := head.Next
        head.Next = prev
        prev = head
        head = nextTemp
    }

    return prev
}

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