文章目錄

• • • 連結清單翻轉循環和遞歸寫法
    • 1.連結清單翻轉循環實作原理圖
    • 2.節點定義
    • 3.連結清單翻轉循環實作代碼
    • 4.連結清單翻轉遞歸實作思想步驟和原理圖
    • 5.遞歸代碼

連結清單翻轉循環和遞歸寫法

1.連結清單翻轉循環實作原理圖

2.節點定義

class Node
{
    public $e;//節點元素
    public $next; //下個節點資訊

    /**
     * 構造函數 設定節點資訊
     * Node constructor.
     * @param $e
     * @param $next
     */
    public function __construct($e, $next=null)
    {
        $this->e = $e;
        $this->next = $next;
    }
}
           

3.連結清單翻轉循環實作代碼

<?php
require 'LinkedList.php';

$linkedList = new LinkedList();

for ($i = 1;$i <= 20;$i++){
    $linkedList->addFirst($i);
}
echo $linkedList->toString();
/**
 * 20->19->18->17->16->15->14->13->12->11->10->9->8->7->6->5->4->3->2->1->null
 */
echo "\n";

function reverse($head){
    $pre = $head;
    $cur = $head->next;
    while ($cur){
        $next = $cur->next;
        $cur->next = $pre;
        $pre = $cur;
        $cur = $next;
    }
    $head->next = null;

    return $pre;
}

$linkedList->setHead(reverse($linkedList->getHead()));


echo $linkedList->toString();
/**
 * 1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->null
 */
echo "\n";
           

示範輸出如下圖：

4.連結清單翻轉遞歸實作思想步驟和原理圖

• 畫圖分析
• 将遞歸函數當成整體，不要跳進遞歸裡邊(因為你的腦袋壓棧不了幾個)
• 寫代碼先處理遞歸到底的情況

  

5.遞歸代碼

public function recursionLinkedList(){
        $this->head = $this->recursion($this->head);
    }

    private function recursion($head){
        if($head->next == null){
            return $head;
        }

        $cur = $head;
        $next = $this->recursion($head->next);//這個想象成一個已經翻轉的連結清單其傳回值是頭
        $head->next->next = $head;//需要得到遞歸整體連結清單的尾部，有一種low辦法就是周遊，但在這裡可以直接取 $head節點的 next 節點，因為其指向的位址沒有變
        $head->next = null;//原來的頭需要指向null

        return $next;//最後需要傳回遞歸整體這個連結清單
    }
           

示範輸出如下圖：

Tips:代碼倉庫：

https://gitee.com/love-for-poetry/arithmetic

、

https://gitee.com/love-for-poetry/data-structure

。

掃碼關注