PHP 再帰を使用してリンク リストを逆にする方法

リンク リストはノードのコレクションである非常に一般的なデータ構造であり、各ノードにはデータ項目と次のノードへのポインタが含まれています。リンク リストは、スタック、キュー、ハッシュ テーブルなどのデータ構造を実装するために使用でき、アルゴリズムの問​​題でよく発生します。

多くのアルゴリズムの問​​題では、リンク リストを逆にする必要があります。リンク リストを反転する基本的な考え方は、リンク リスト内の各ノードを前のノードにポイントし、最終的に最初のノードをリンク リストの末尾ノードにすることです。この操作は、リンク リストの検索、結合、並べ替えなどのさまざまなシナリオに適用できます。

この記事では、PHP を使用して、リンク リストを再帰的に反転する機能を実装する方法を紹介します。連結リストや再帰などの概念についてよく知らない場合は、まず関連する基礎知識を自分で学習できます。

実装方法

リンク リストを再帰的に反転するプロセスでは、リンク リストを最初のノードと残りの部分の 2 つの部分に分割する必要があります。残りの部分を反転した後、反転したリストの最後に最初のノードを挿入します。このプロセスは再帰を使用して実装できます。具体的な実装は次のとおりです。

/**
 * 反转链表
 * @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;
}

コード分析

上記のコードでは、まず基本ケース、つまりノードが空の場合、またはノードが空の場合を処理します。次のノードは空です。ノード自体を直接返します。次に、残りのノードを再帰的に処理して、逆リンク リストを取得します。

次に、現在のノードを反転リストの末尾に挿入します。具体的には、現在のノード $head の次のノード $head->next の次のノードを指し、$head の次のノードを空にし、最後に反転したヘッド ノード $newHead を返します。

さらに、上記のコードをよりよく理解するために、リンク リスト ノードの定義も追加する必要があります:

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

テスト ケース

上記を確認するために コードが正しいことを確認するために、次のテスト ケースを作成できます:

$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);

上記のテスト ケースを実行すると、次の出力結果を取得できます:

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] => 
                                )

                        )

                )

        )

)

結論

この記事では、PHP 再帰を使用してリンク リストの反転操作を実装する方法を紹介します。上記のデモンストレーションを通じて、リンク リスト問題を解決する際の再帰的アルゴリズムの優位性がわかります。実際の開発では、実際のシナリオに基づいて問題を解決するために最適なアルゴリズムを選択する必要があります。この記事が読者にとって役立つことを願っています。

以上がPHP 再帰を使用してリンク リストを逆にする方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。