摘要：因?yàn)樯婕爸羔槪覀冇靡脕砟M，所以讀者應(yīng)該有面向?qū)ο蟮闹R(shí)貯備。引文因?yàn)樯婕皟?nèi)存，常常會(huì)有一些程序的邊界限制，需要擁有一定嚴(yán)密的邏輯去保證代碼的魯棒性和健壯性，所以這個(gè)知識(shí)點(diǎn)是面試的常考點(diǎn)。

tips：因?yàn)樯婕爸羔?，我們用引用來模擬，所以讀者應(yīng)該有面向?qū)ο蟮闹R(shí)貯備。

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

因?yàn)樯婕皟?nèi)存，常常會(huì)有一些程序的邊界限制，需要programer擁有一定嚴(yán)密的邏輯去保證代碼的魯棒性和健壯性，所以這個(gè)知識(shí)點(diǎn)是面試的?？键c(diǎn)。下面我們看看PHP的單鏈表實(shí)現(xiàn)（附?？碱}目實(shí)現(xiàn)）：

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


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

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

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

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

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

    }

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

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

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


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

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

        /*    第i步    */
        if($p == null){    #說明鏈表已經(jīng)結(jié)束，不存在i節(jié)點(diǎn),過濾掉i大于鏈表長(zhǎng)度的情況，以為若i大于鏈表長(zhǎng)度，則上面循環(huán)會(huì)跳出直接進(jìn)入判斷然后返回
            echo "不存在i節(jié)點(diǎn)" ;
            exit;
        }else{
            /*    標(biāo)準(zhǔn)的刪除語句    */
            $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指向第一個(gè)節(jié)點(diǎn)
        
        while($p != null ){
            $q = $p->next;    #保證節(jié)點(diǎn)在向后移動(dòng)
            unset($p);
            $p = $q;
        }
    }

    /**
     * Question1:輸出倒數(shù)第K個(gè)節(jié)點(diǎn)
     * @param $head object 鏈表
     * @param $k     int    序號(hào)
     */
    function FindKthToTail($head, $k){
        /*    如果鏈表為空或者k不合法 返回null    */
        if($head == null || $k<=0){
            return null;
        }
        
        /*    這里采用了復(fù)雜度為O(n)的算法，需要準(zhǔn)備兩個(gè)節(jié)點(diǎn)    */
        $behind = $head;    #指向鏈表的第一個(gè)節(jié)點(diǎn)
       
        /*    算法思路：準(zhǔn)備兩個(gè)指針，假如第一個(gè)指針走到n-1（即鏈表末尾），第二個(gè)指針走到倒數(shù)k的位置，兩者之間相差(n-1)-(n-k) = k-1 */
        for($i=0;$i<$k-1;$i++){
            /*    讓第一個(gè)指針先走k-1個(gè)單位，如果不為空，則指針向后移動(dòng)    */
            /*    注意：這里有一個(gè)隱藏的條件，就是鏈表的長(zhǎng)度有可能小于k，我們不不遍歷完整個(gè)鏈表是無法知道其長(zhǎng)度的    */
            if($head->next != null){
                $head = $head->next;
            }else{
                return ;
            }
        }
        /*    當(dāng)?shù)谝粋€(gè)指針走到k-1且還不為空，這時(shí)讓第二個(gè)指針開始走，當(dāng)?shù)谝粋€(gè)指針走到n-1的時(shí)候，第二個(gè)指針也走到了倒數(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é)點(diǎn) ，這里是根節(jié)點(diǎn)
    $cur  = $pre->next; #當(dāng)前節(jié)點(diǎn)    2     例：1->2->3
    $next = null;    #后一節(jié)點(diǎn)
   
    /*    鏈表存在且不為空    */
    while(!$cur){
        $next = $cur->next;    #用一個(gè)變量暫時(shí)存儲(chǔ)后一節(jié)點(diǎn)，因?yàn)橐坏┣懊娣崔D(zhuǎn)，就斷鏈了
        $cur->next = $pre;    #將前一節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)的后一節(jié)點(diǎn)，是為反轉(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);