摘要：一定要認(rèn)真看分析注釋題目要求題目描述輸入一個鏈表，從尾到頭打印鏈表每個節(jié)點的值。分析因為鏈表只有知道當(dāng)前結(jié)點才能知道下一結(jié)點，所以不可能直接從后往前打印。

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

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

分析：
因為鏈表只有知道當(dāng)前結(jié)點才能知道下一結(jié)點，所以不可能直接從后往前打印。這種逆序的算法（策略）我們常用棧這種數(shù)據(jù)結(jié)構(gòu)來解決，所以我們的基本思路為，先將鏈表壓入棧，再彈出，但是這樣做我們需要遍歷兩次才能得出答案，更奇妙的解決方案為一次將結(jié)點值插入數(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;
}

測試地址：https://www.nowcoder.com/prac...

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

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

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

測試地址：https://www.nowcoder.com/prac...

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

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

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

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

測試地址：https://www.nowcoder.com/prac...

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

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

val = $x;
    }
}*/
function MergeList($pHead1, $pHead2)
{
    // write code here
    /*
         先用頭結(jié)點比較大小，小的壓入數(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){     #這里作判斷的目的主要是在遞歸過程中可能會有一方先遍歷結(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;
    
}

測試地址：https://www.nowcoder.com/prac...

題目描述：
給定一個鏈表

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

分析：
最近segment插圖好像出了點問題，我給個鏈接吧環(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){ #此時slow為頭結(jié)點
                $fast = $fast->next;
                $slow = $slow->next;
            }
            if($fast == $slow){
                    return $fast;
                }
   
        }
    }
   
    return null;
}

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

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

/**
* @param  $monkeys Array 預(yù)設(shè)數(shù)組
* @param  $m.    Int。   預(yù)設(shè)剔除序號
* @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);
    }
}