摘要：一定要認(rèn)真看分析注釋題目要求題目描述輸入一個(gè)鏈表，從尾到頭打印鏈表每個(gè)節(jié)點(diǎn)的值。分析因?yàn)殒湵碇挥兄喇?dāng)前結(jié)點(diǎn)才能知道下一結(jié)點(diǎn)，所以不可能直接從后往前打印。

一定要認(rèn)真看 分析 | 注釋 | 題目要求

題目描述：
輸入一個(gè)鏈表，從尾到頭打印鏈表每個(gè)節(jié)點(diǎn)的值。

分析：
因?yàn)殒湵碇挥兄喇?dāng)前結(jié)點(diǎn)才能知道下一結(jié)點(diǎn)，所以不可能直接從后往前打印。這種逆序的算法（策略）我們常用棧這種數(shù)據(jù)結(jié)構(gòu)來(lái)解決，所以我們的基本思路為，先將鏈表壓入棧，再?gòu)棾觯沁@樣做我們需要遍歷兩次才能得出答案，更奇妙的解決方案為一次將結(jié)點(diǎn)值插入數(shù)組頭部，一次便可以滿足題目要求，代碼如下：

val = $x;
    }
}*/

function printListFromTailToHead($head)
{
    $stack = [];
    if(!$head){
        return $stack;
    }
    while($head){
        array_unshift($stack,$head->val);   #array_unshift返回頭插后的數(shù)組單元數(shù)目
        $head = $head->next;
    }
    return $stack;
}

測(cè)試地址：https://www.nowcoder.com/prac...

題目描述：
輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。

分析：
前提：鏈表是動(dòng)態(tài)分配的，事先不能知道鏈表的總長(zhǎng)度
一般思路：遍歷鏈表，得出長(zhǎng)度，輸出結(jié)點(diǎn)
面試思路：準(zhǔn)備兩個(gè)指針，假如第一個(gè)指針走到n-1（即鏈表末尾），第二個(gè)指針走到倒數(shù)k的位置，兩者之間相差(n-1)-(n-k) = k-1，先讓一個(gè)指針走到k-1，第二個(gè)指針原地等待，然后讓第二個(gè)指針和第一個(gè)指針同時(shí)走，走到末尾，找到k，代碼如下：

next != null){
                $head = $head->next;
            }else{
                 /*    注意：這里有一個(gè)隱藏的條件，就是鏈表的長(zhǎng)度有可能小于k，當(dāng)我們走到k-1時(shí)鏈表就已經(jīng)遍歷結(jié)束，這種情況同樣非法    */
                return null;
            }
        }
        /*    當(dāng)?shù)谝粋€(gè)指針走到k-1且還不為空，這時(shí)讓第二個(gè)指針開(kāi)始走，當(dāng)?shù)谝粋€(gè)指針走到n-1的時(shí)候，第二個(gè)指針也走到了倒數(shù)第k的位置，即所求    */
        while($head->next != null){
            $head = $head->next;
            $behind = $behind->next;
        }
        return $behind;
    }

測(cè)試地址：https://www.nowcoder.com/prac...

題目描述：
輸入一個(gè)鏈表，反轉(zhuǎn)鏈表后，輸出鏈表的所有元素。

分析：
畫圖最佳 主要就是運(yùn)用臨時(shí)節(jié)點(diǎn) 看注釋

next;    #首先將鏈上第二個(gè)位置的值放在臨時(shí)容器中
            $pHead->next = $cur;    #將第二個(gè)位置賦一個(gè)空值 保持鏈的關(guān)系

            $cur = $pHead;          #將第一個(gè)位置的值賦給第二個(gè)位置
            $pHead = $tmp;          #將原第二個(gè)位置的值賦給頭結(jié)點(diǎn)
        }
        return $cur;
    }

測(cè)試地址：https://www.nowcoder.com/prac...

題目描述：
輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。

分析：
畫圖最佳 先用頭結(jié)點(diǎn)比較大小，小的壓入數(shù)組，大的和小的的后一位繼續(xù)比較

val = $x;
    }
}*/
function MergeList($pHead1, $pHead2)
{
    // write code here
    /*
         先用頭結(jié)點(diǎn)比較大小，小的壓入數(shù)組，大的和小的的后一位繼續(xù)比較
    */
    if($pHead1 == null && $pHead2 == null){
        return null;
    }
    if($pHead1 == null){
        return $pHead2;
    }
    if($pHead2 == null){
        return $pHead1;
    }

    $target = array();

    if($pHead1 != null && $pHead2 != null){     #這里作判斷的目的主要是在遞歸過(guò)程中可能會(huì)有一方先遍歷結(jié)束
        if($pHead1->val >= $pHead2->val){
            $target = $pHead2;
            $target->next = MergeList($pHead1,$pHead2->next);
        }else{
            $target = $pHead1;
            $target->next = MergeList($pHead1->next,$pHead2);
        }
    }
    return $target;
    
}

測(cè)試地址：https://www.nowcoder.com/prac...

題目描述：
給定一個(gè)鏈表

1.判斷鏈表是否有環(huán)
2.鏈表起始結(jié)點(diǎn)（入口結(jié)點(diǎn)）

分析：
最近segment插圖好像出了點(diǎn)問(wèn)題，我給個(gè)鏈接吧環(huán)形鏈表

function EntryNodeOfLoop($pHead)
{
    // write code here
    if($pHead == null){
        return null;
    }
    $fast = $pHead;
    $slow = $pHead;
    
    while($fast != null && $fast->next != null){
        $fast = $fast->next->next;
        $slow = $slow->next;
        if($fast == $slow){  #存在環(huán)
            $slow = $pHead;
            while($fast != $slow){ #此時(shí)slow為頭結(jié)點(diǎn)
                $fast = $fast->next;
                $slow = $slow->next;
            }
            if($fast == $slow){
                    return $fast;
                }
   
        }
    }
   
    return null;
}

題目描述：
“約瑟夫環(huán)”是一個(gè)數(shù)學(xué)的應(yīng)用問(wèn)題：一群猴子排成一圈，按1,2,…,n依次編號(hào)。然后從第1只開(kāi)始數(shù)，數(shù)到第m只,把它踢出圈，從它后面再開(kāi)始數(shù)， 再數(shù)到第m只，在把它踢出去…，如此不停的進(jìn)行下去， 直到最后只剩下一只猴子為止，那只猴子就叫做大王。要求編程模擬此過(guò)程，輸入m、n, 輸出最后那個(gè)大王的編號(hào)。

分析：
第一個(gè)出列的猴子肯定是a[1]=m(mod)n，設(shè)此時(shí)某個(gè)猴子的新編號(hào)是i，他原來(lái)的編號(hào)就是(i+a[1])%n

/**
* @param  $monkeys Array 預(yù)設(shè)數(shù)組
* @param  $m.    Int。   預(yù)設(shè)剔除序號(hào)
* @param  $cur.  Int。   標(biāo)記
*/
function JosephCircle($monkeys , $m , $current = 0){
    $number = count($monkeys);
    $num = 1;
    if(count($monkeys) == 1){
        echo $monkeys[0];
        return;
    }
    else{
        while($num++ < $m){
            $current++ ;
            $current = $current%$number;
        }
        echo $monkeys[$current];
        array_splice($monkeys , $current , 1);  #剔除
        JosephCircle($monkeys , $m , $current);
    }
}