鏈表題目總結

鏈表基本操作

對鏈表進行增刪改查等基本操作。注意，很多鏈表的題目使用虛擬頭結點操作起來會更加方便。每次對應頭結點的情況都要單獨處理，所以使用虛擬頭結點的技巧，就可以解決這個問題。

反轉鏈表

可以使用頭插法，也可以直接修改節點的指向（這種思想有兩種實現方法，迭代和遞歸）

刪除倒數第n個節點

采用虛擬頭結點和雙指針的思想，可以一次遍歷就找到要刪除的節點。

鏈表相交

如果用兩個指針 p1 和 p2 分別在兩條鏈表上前進，我們可以讓 p1 遍歷完鏈表 A 之后開始遍歷鏈表 B，讓 p2 遍歷完鏈表 B 之后開始遍歷鏈表 A，這樣相當于「邏輯上」兩條鏈表接在了一起。如果這樣進行拼接，就可以讓 p1 和 p2 同時進入公共部分，也就是同時到達相交節點 c1。

環形鏈表

定義快慢指針，慢指針每次走1步，快指針每次走2步。首先判斷是否有環，如果有環的話，快指針一定先進環，慢指針進環后第一圈快慢指針一定相遇，沒有環的話返回null。如果相遇，再定義兩個指針一個從相遇的節點開始，一個從第一個節點開始，每次都各走一步，兩個指針再次相遇的時候就是入環節點。

---