演算法面試筆試總結

在單資料結構（即在題目中明確提到了某種資料結構，沒有摻雜，也沒有背景，只是進行某些特定操作）的題型中，鍊錶是一大類，而單鏈表因為其特定的儲存結構和讀取方法又成為考查的重點。

列舉題目如下

(注：以下題目的給定node節點全部為如下定義方式)

給定單鏈表的頭節點node head.給出將此鍊錶反轉的方法。

給定兩個單鏈表，表頭分別為head1和head2.判斷兩個鍊錶是否相交，如果不相交返回null，如果相交，則給出相交的第乙個交點。

對題目進行簡單分析後不難得出，因為鍊錶的特殊儲存結構，使得其在儲存結構上如果交叉則一定為「y」型或者為「v」型，不可能為「x」型。所以相交只需求出第乙個交點。

演算法具體實現可以如下

給定乙個單鏈表，頭節點為node head.找出其倒數第n個節點。

演算法思路即為給定兩個node,起初在head 節點向後走的時候，使另外乙個節點node1託管這個鍊錶的頭，在head向後走了n個節點後，node1向後遍歷，在head為null時，node1即指向了倒數第n個節點。

演算法可以如下：

刪除單鏈表中的某節點，或者不知道頭節點，這時需要保證此節點不是最後乙個節點，或者即使讓你知道頭節點，但是不允許迴圈遍歷。

思路即為，因為知道這個節點，不遍歷，能找到的只有他下乙個節點以及他本身，這樣的話將他下乙個節點的資料和next屬性付給當前節點，並將下一節點刪除即可，偷梁換柱，達到效果。

**可以如下：

如何判斷乙個鍊錶是否有環存在。

思路為定義兩個指標，即好像在操場上跑步，只要兩個人速度不一樣，速度快的肯定會有套速度慢的一圈的時刻。難點的還可以加上找到環的入口點，這裡暫且不說。

**可以如下

給定兩個遞增的鍊錶，頭節點分別為head1,head2,如何操作使之合併為乙個遞減的鍊錶。

思路為經典的二路歸併排序演算法，建立乙個新鍊錶，開始遍歷兩個鍊錶，將數值小的插入到新鍊錶的末尾，並且將該節點原來指標向前移動一次，繼續比較，大多數情況在遍歷玩乙個鍊錶後，另外乙個會有剩餘節點，需要處理。

**可以如下