摘要：因為涉及指針，我們用引用來模擬，所以讀者應(yīng)該有面向?qū)ο蟮闹R貯備。引文因為涉及內(nèi)存，常常會有一些程序的邊界限制，需要擁有一定嚴密的邏輯去保證代碼的魯棒性和健壯性，所以這個知識點是面試的?？键c。

tips：因為涉及指針，我們用引用來模擬，所以讀者應(yīng)該有面向?qū)ο蟮闹R貯備。

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

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

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


/**
 * TODO:構(gòu)建單鏈表 
 */
Class SingleLinkList{

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

    /*    尾插法創(chuàng)建鏈表    */
    public function rearInsert($n){
        /*    新建一個尾節(jié)點    */
        $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個數(shù)據(jù)
     * @param $list object 待插入的鏈表
     * @param $i     int     節(jié)點序號
     */

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

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

    }

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

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

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


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

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

        /*    第i步    */
        if($p == null){    #說明鏈表已經(jīng)結(jié)束，不存在i節(jié)點,過濾掉i大于鏈表長度的情況，以為若i大于鏈表長度，則上面循環(huán)會跳出直接進入判斷然后返回
            echo "不存在i節(jié)點" ;
            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 "輸入?yún)?shù)不合法";
            exit;
        }
        $p = $list->next;    #設(shè)置p指向第一個節(jié)點
        
        while($p != null ){
            $q = $p->next;    #保證節(jié)點在向后移動
            unset($p);
            $p = $q;
        }
    }

    /**
     * Question1:輸出倒數(shù)第K個節(jié)點
     * @param $head object 鏈表
     * @param $k     int    序號
     */
    function FindKthToTail($head, $k){
        /*    如果鏈表為空或者k不合法 返回null    */
        if($head == null || $k<=0){
            return null;
        }
        
        /*    這里采用了復(fù)雜度為O(n)的算法，需要準備兩個節(jié)點    */
        $behind = $head;    #指向鏈表的第一個節(jié)點
       
        /*    算法思路：準備兩個指針，假如第一個指針走到n-1（即鏈表末尾），第二個指針走到倒數(shù)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 ;
            }
        }
        /*    當?shù)谝粋€指針走到k-1且還不為空，這時讓第二個指針開始走，當?shù)谝粋€指針走到n-1的時候，第二個指針也走到了倒數(shù)第k的位置，即所求    */
        while($head->next != null){
            $head = $head->next;
            $behind = $behind->next;
        }
        return $behind;
    }

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

        #指針后移
        $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);