Cara menggunakan rekursi PHP untuk membalikkan senarai terpaut

Senarai terpaut ialah struktur data yang sangat biasa, iaitu koleksi nod Setiap nod mengandungi item data dan penunjuk ke nod seterusnya. Senarai terpaut boleh digunakan untuk melaksanakan struktur data seperti susunan, baris gilir dan jadual cincang, dan sering ditemui dalam masalah algoritma.

Dalam banyak masalah algoritma, senarai terpaut perlu diterbalikkan. Idea asas untuk membalikkan senarai terpaut adalah untuk menghalakan setiap nod dalam senarai terpaut ke nod sebelumnya, dan akhirnya menjadikan nod pertama sebagai nod ekor senarai terpaut. Operasi ini boleh digunakan dalam pelbagai senario seperti mencari, menggabungkan dan mengisih senarai terpaut.

Artikel ini akan memperkenalkan cara menggunakan PHP untuk melaksanakan fungsi membalikkan senarai terpaut secara rekursif. Jika anda tidak tahu banyak tentang konsep seperti senarai terpaut dan rekursi, anda boleh belajar sendiri pengetahuan asas yang berkaitan terlebih dahulu.

Kaedah pelaksanaan

Dalam proses membalikkan senarai terpaut secara rekursif, senarai terpaut perlu dipecahkan kepada dua bahagian: nod pertama dan bahagian selebihnya. Selepas membalikkan bahagian yang tinggal, masukkan nod pertama pada penghujung senarai terbalik. Proses ini boleh dilaksanakan menggunakan rekursi. Pelaksanaan khusus adalah seperti berikut:

/**
 * 反转链表
 * @param ListNode $head 头节点
 * @return ListNode|null 反转后的头节点
 */
function reverseList($head) {
    // base case
    if ($head == null || $head->next == null) {
        return $head;
    }
    
    // 反转剩余部分
    $newHead = reverseList($head->next);
    
    // 将当前节点插入到反转后的链表末尾
    $head->next->next = $head;
    $head->next = null;
    
    return $newHead;
}

Analisis kod

Dalam kod di atas, kami mula-mula memproses kes asas, iaitu, nod kosong atau nod seterusnya kosong terus mengembalikan nod itu sendiri. Kemudian, kami memproses secara rekursif nod yang tinggal untuk mendapatkan senarai terpaut terbalik.

Seterusnya, kami memasukkan nod semasa ke penghujung senarai terbalik. Secara khusus, kami menunjuk nod seterusnya bagi nod seterusnya $head->bersebelahan nod semasa $head, kosongkan nod seterusnya $head, dan akhirnya mengembalikan nod kepala terbalik $newHead.

Selain itu, untuk lebih memahami kod di atas, kita juga perlu menambah definisi nod senarai terpaut:

class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val) {
        $this->val = $val;
    }
}

Kes ujian

Untuk mengesahkan ketepatan kod di atas, kita boleh menulis kes ujian berikut:

$head = new ListNode(1);
$head->next = new ListNode(2);
$head->next->next = new ListNode(3);
$head->next->next->next = new ListNode(4);
$head->next->next->next->next = new ListNode(5);

$newHead = reverseList($head);

print_r($newHead);

Melaksanakan kes ujian di atas, kita boleh mendapatkan output berikut:

ListNode Object
(
    [val] => 5
    [next] => ListNode Object
        (
            [val] => 4
            [next] => ListNode Object
                (
                    [val] => 3
                    [next] => ListNode Object
                        (
                            [val] => 2
                            [next] => ListNode Object
                                (
                                    [val] => 1
                                    [next] => 
                                )

                        )

                )

        )

)

Kesimpulan

Artikel ini memperkenalkan cara menggunakan rekursi PHP untuk melaksanakan operasi pembalikan senarai terpaut. Melalui demonstrasi di atas, kita dapat melihat keunggulan algoritma rekursif dalam menyelesaikan masalah senarai terpaut. Dalam pembangunan sebenar, kita perlu memilih algoritma yang paling sesuai untuk menyelesaikan masalah berdasarkan senario sebenar. Semoga artikel ini bermanfaat kepada pembaca!

Atas ialah kandungan terperinci Cara menggunakan rekursi PHP untuk membalikkan senarai terpaut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!