鏈表面試常見合集

##給定單鏈表，檢測是否有環。如果有環，則求出進入環的第一個節點。 判斷單向鏈表是否有環，可以採用快指針與慢指針的方式來解決。即定義一個快指針fast和一個慢指針slow，使得fast每次跳躍兩個節點，slow每次跳躍一個節點。如果鏈表沒有環的話，則slow與fast永遠不會相遇（這裡鏈表至少有兩個節點）；如果有環，則fast與slow將會在環中相遇。 然後獲取環的入口點方法如圖所示：

##給定兩個單鏈表（鏈表自身無環），檢測兩個鏈表是否有交點，如果有返回第一個交點。 檢測兩個單鏈表是否有交點是很容易的，因為如果兩個鏈表有交點，那麼這兩個鏈表的最後一個節點必須相同，所以只需比較最後一個節點即可。但是這種方案是無法求出第一個交點的，所以需要另闢蹊徑。另外，判斷是否有交點可以轉換成鏈表是否有環的問題。讓一個鏈表的最後一個節點指向第二個鏈表的頭結點，這樣的話，如果相交，則新的鏈表是存在環的，並且交點便是環的入口點。

##給定兩個單鏈表（不確定是否帶環），判斷是否有交點 先判斷兩個鏈表是否帶環； 　　i).如果兩個都不帶環，可以用：判斷兩個無環單鏈表是否有交點。 　　ii).兩個都帶環：找到兩個入環點r1,r2，環1的入環點為r1，從r1開始遍歷一圈，每個結點如r2比較 　 iii).一個帶環一個不帶環，則肯定不相交。

##給定單鏈表頭結點，刪除鏈表中倒數第k個結點 這個問題的關鍵是需要獲取倒數第k個節點。如何獲取呢？這裡，需要兩個指針p和q，p指向頭結點，q指向距離頭結點為k的節點。這樣p和q每次遍歷一個節點，當q遍歷到末尾的時候，p指向的節點即為倒數第k個節點，然後刪除即可。

##只給定單鏈表中某個結點p（並非最後一個結點，即p->next!=NULL）指針，刪除該結點； ##只給定單鏈表中某個結點p（非空結點），在p前面插入一個結點。 上訴兩種方法的原理都是一樣的。