摘要：因為涉及指針，我們用引用來模擬，所以讀者應該有面向對象的知識貯備。引文因為涉及內存，常常會有一些程序的邊界限制，需要擁有一定嚴密的邏輯去保證代碼的魯棒性和健壯性，所以這個知識點是面試的常考點。

tips：因為涉及指針，我們用引用來模擬，所以讀者應該有面向對象的知識貯備。

你可以把鏈表簡單理解為動態數組，它不需要一塊一塊的開辟空間，同時，你又要注意，它存在的主要意義或者說使用場景主要是”指針功能“，它能夠指來指去，對一些應用特別是內存管理起到了關鍵作用。

因為涉及內存，常常會有一些程序的邊界限制，需要programer擁有一定嚴密的邏輯去保證代碼的魯棒性和健壯性，所以這個知識點是面試的常考點。下面我們看看PHP的單鏈表實現（附常考題目實現）：

data = $val;
        $this->next = $nex;
    }
}


/**
 * TODO:構建單鏈表 
 */
Class SingleLinkList{

    /*    頭插法創建鏈表 n為節點總數    */
    public function headInsert($n){
        /*    新建一個頭節點    */
        $head = new Node(null,null);
        for($i=$n;$i>0;$i--){
            $newNode = new Node($i,null);
            $head->data = $newNode->data;    #新建節點賦值給頭節點
            $newNode->next = $head->next;    #將頭節點的后繼節點作為新建節點的后繼節點，相當于在原頭節點和頭節點的后繼節點中間添加了一個新節點
            $head->next = $newNode;            #將新建節點作為頭節點的后繼節點，這時候原本頭節點的后繼節點已經改變了
        }
        return $head;
    }

    /*    尾插法創建鏈表    */
    public function rearInsert($n){
        /*    新建一個尾節點    */
        $rear = new Node(null,null);
        for($j=0;$j<$n;$j++){
            $newNode = new Node($j,null);
            $rear->data = $newNode->data;

            //$newNode = $rear->next;
            $rear->next = $newNode;
            $rear = $newNode;
        }
        return $rear;
    }


    /**
     * TODO:讀取鏈表中第i個數據
     * @param $list object 待插入的鏈表
     * @param $i     int     節點序號
     */

    public function readIThNode($list,$i){
        /*    如果鏈表為空或者i小等于0    */
        if($list == null || $i<=0){
            echo "輸入參數不合法";
            return ;
        }
        /*        */
        $p = $list->next;    #設置p指向第一個節點（即頭節點的后繼節點））
        $j=0;                #計時器必須初始化
        while($p && $j<$i ){
            $p = $p->next;
            ++$j;
        }

        /*    第i步    */
        if($p == null){    #說明鏈表已經結束，不存在i節點,過濾掉i大于鏈表長度的情況（因為節點是散列的，事先并不知道其長度）
            echo "i長度大于鏈表長度" ;
            exit;
        }else{
            $e = $p->data;    #第i個節點存在 ，返回
            return $e;
        }

    }

    /**
     * TODO:在鏈表的第i個位置之前插入節點e
     * @param $list object 待插入的鏈表
     * @param $i     int     節點序號
     * @param $e    object 待插入的節點
     */
    public function Insert($list,$i,$e){
        if($e == null){
            echo "待插入節點為空";
            exit;
        }
        $p = $list->next;    #設置p指向第一個節點
        $j=0;                #計時器必須初始化

        while($p && $j<$i ){
            $p = $p->next;    #保證節點在向后移動
            ++$j;
        }

        /*    第i步    */
        if($p == null){    #說明鏈表已經結束，不存在i節點,過濾掉i大于鏈表長度的情況（因為節點是散列的，事先并不知道其長度）
            echo "不存在i節點" ;
            exit;
        }else{
            /*    標準的插入語句（頭插法）    */
            $e->next = $p->next;
            $p->next = $e;
            return $list;
        }
    }


    /**
     * TODO:刪除鏈表的第i個節點，并返回該節點的值
     * @param $list object 待插入的鏈表
     * @param $i    int    節點序號
     */
    public function Delete($list,$i){
        if($list == null || $i<=0){
            echo "輸入參數不合法";
            exit;
        }
        $p = $list->next;    #設置p指向第一個節點
        $j=0;                #計時器必須初始化

        while($p && $j<$i ){
            $p = $p->next;    #保證節點在向后移動
            ++$j;
        }

        /*    第i步    */
        if($p == null){    #說明鏈表已經結束，不存在i節點,過濾掉i大于鏈表長度的情況，以為若i大于鏈表長度，則上面循環會跳出直接進入判斷然后返回
            echo "不存在i節點" ;
            exit;
        }else{
            /*    標準的刪除語句    */
            $q = $p->next;
            $p->next = $q->next;
            $e = $q->data;
            unset($q);
            return $e;
        }
    }

    /**
     * TODO:刪除整張鏈表
     * @param $list object 待插入的鏈表
     */
    public function DeleteAll($list){
        if($list == null ){
            echo "輸入參數不合法";
            exit;
        }
        $p = $list->next;    #設置p指向第一個節點
        
        while($p != null ){
            $q = $p->next;    #保證節點在向后移動
            unset($p);
            $p = $q;
        }
    }

    /**
     * Question1:輸出倒數第K個節點
     * @param $head object 鏈表
     * @param $k     int    序號
     */
    function FindKthToTail($head, $k){
        /*    如果鏈表為空或者k不合法 返回null    */
        if($head == null || $k<=0){
            return null;
        }
        
        /*    這里采用了復雜度為O(n)的算法，需要準備兩個節點    */
        $behind = $head;    #指向鏈表的第一個節點
       
        /*    算法思路：準備兩個指針，假如第一個指針走到n-1（即鏈表末尾），第二個指針走到倒數k的位置，兩者之間相差(n-1)-(n-k) = k-1 */
        for($i=0;$i<$k-1;$i++){
            /*    讓第一個指針先走k-1個單位，如果不為空，則指針向后移動    */
            /*    注意：這里有一個隱藏的條件，就是鏈表的長度有可能小于k，我們不不遍歷完整個鏈表是無法知道其長度的    */
            if($head->next != null){
                $head = $head->next;
            }else{
                return ;
            }
        }
        /*    當第一個指針走到k-1且還不為空，這時讓第二個指針開始走，當第一個指針走到n-1的時候，第二個指針也走到了倒數第k的位置，即所求    */
        while($head->next != null){
            $head = $head->next;
            $behind = $behind->next;
        }
        return $behind;
    }

    
    /**
     * Question2:反轉鏈表
     * @param $head object 鏈表
     */
    public function ReverseList($pHead)
{
    /*    如果鏈表為空，返回null    */
    if($pHead == null){
        return null;
    }
    $pre  = $pHead; #前一節點 ，這里是根節點
    $cur  = $pre->next; #當前節點    2     例：1->2->3
    $next = null;    #后一節點
   
    /*    鏈表存在且不為空    */
    while(!$cur){
        $next = $cur->next;    #用一個變量暫時存儲后一節點，因為一旦前面反轉，就斷鏈了
        $cur->next = $pre;    #將前一節點作為當前節點的后一節點，是為反轉

        #指針后移
        $pre = $cur;    
        $cur = $next;   
    }
    return $pre;
}
}
$object = new SingleLinkList();
$result = (new SingleLinkList)->headInsert(4);
$pre = $object->ReverseList($result);
//$behind = $object->FindKthToTail($result,1);

// $e = $object->readIThNode($result,2);
// echo $e;

// $newNode = new Node(6,null);
// $newList = $object->Insert($result,2,$newNode);

// $e = $object->Delete($result,2);

 echo "
";
// print_r($result);
print_r($pre);