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

一定要認真看 分析 | 注釋 | 題目要求

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

分析：
因為鏈表只有知道當前結點才能知道下一結點，所以不可能直接從后往前打印。這種逆序的算法（策略）我們常用棧這種數據結構來解決，所以我們的基本思路為，先將鏈表壓入棧，再彈出，但是這樣做我們需要遍歷兩次才能得出答案，更奇妙的解決方案為一次將結點值插入數組頭部，一次便可以滿足題目要求，代碼如下：

val = $x;
    }
}*/

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

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

題目描述：
輸入一個鏈表，輸出該鏈表中倒數第k個結點。

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

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

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

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

分析：
畫圖最佳 主要就是運用臨時節點 看注釋

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

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

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

題目描述：
輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則。

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

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

    $target = array();

    if($pHead1 != null && $pHead2 != null){     #這里作判斷的目的主要是在遞歸過程中可能會有一方先遍歷結束
        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.判斷鏈表是否有環
2.鏈表起始結點（入口結點）

分析：
最近segment插圖好像出了點問題，我給個鏈接吧環形鏈表

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){  #存在環
            $slow = $pHead;
            while($fast != $slow){ #此時slow為頭結點
                $fast = $fast->next;
                $slow = $slow->next;
            }
            if($fast == $slow){
                    return $fast;
                }
   
        }
    }
   
    return null;
}

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

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

/**
* @param  $monkeys Array 預設數組
* @param  $m.    Int。   預設剔除序號
* @param  $cur.  Int。   標記
*/
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);
    }
}