深入解析鏈表：從基礎分類到進階應用與優化

鏈表的核心分類與特性

鏈表作為基礎數據結構，根據指針方向與連接方式主要分為三類：

單鏈表

節點僅包含指向後繼節點的指針。插入操作常見兩種模式：頭插法僅需維護頭節點，適合模擬棧（LIFO）結構；尾插法需同時維護頭尾指針，天然適合模擬隊列（FIFO）結構。

雙向鏈表

每個節點擁有前驅與後繼兩個指針，支持雙向遍歷。此特性使其成為瀏覽器歷史記錄、音樂播放列表等需要前後導航場景的首選結構。

循環鏈表

尾節點指向頭節點形成閉環，常見於面試題中的環檢測問題，也是實現循環隊列、多任務輪詢調度的基礎結構。

鏈表節點刪除的兩種經典實現

方式一：雙指針法

維護 current（當前節點）與 previous（前驅節點）指針。遍歷至目標節點時，執行 previous->next = current->next 並釋放 current。需特別處理刪除頭節點的邊界情況。

方式二：二級指針法

使用 Node** current 間接引用節點指針，配合臨時變量 entry。刪除時直接執行 *current = entry->next 並釋放 entry。此法巧妙統一了頭節點與普通節點的刪除邏輯，代碼更簡潔健壯。

基於內存池的鏈表優化

傳統鏈表頻繁調用系統分配/釋放內存（malloc/free 或 new/delete），存在三大弊端：

1. 頻繁系統調用導致性能開銷大；
2. 內存碎片化，不利於大塊內存分配；
3. 節點內存分散導致 Cache Miss 率高。

解決方案：預先構建內存池，插入時從池中取節點，刪除時歸還節點。優勢在於：零系統調用開銷、無內存碎片、節點連續分布提升緩存命中率。

鏈表反轉：三種面試必考思路

思路一：三指針迭代法

維護 prev、curr、next 三指針，遍歷過程中逐個反轉指針方向，時間 O(n)，空間 O(1)。

思路二：頭插法構建新表

將第 3 至 N 個節點依次頭插到頭節點之後，最後將原頭節點移至新表尾部。本質同上但思維角度不同。

思路三：遞歸法

遞歸處理 head->next 之後的子鏈表，回溯時修改 head 與 head->next 的指向。代碼極簡但需注意棧溢出風險。

倒序打印鏈表

• 遞歸：利用系統調用棧，先遞歸到表尾再回溯打印。
• 棧模擬：順序遍歷入棧（STL stack），再依次出棧打印，顯式控制內存更安全。

環形鏈表完整解析（快慢指針法）

1. 判斷是否有環

快指針每步 2 格，慢指針每步 1 格，相遇即有環。

2. 求環長度

記錄相遇點，一指針原地，另一指針繼續繞環，再次相遇時慢指針走過步數即環長。

3. 找環入口

數學證明：相遇點到入口距離 = 頭節點到入口距離。雙指針分別從頭節點與相遇點出發，同速前進，相遇點即入口。

4. 帶環鏈表總長度

非環部分長度 + 環長度（問題 2 + 問題 3）。

間接尋址：數組與鏈表的結合體

使用指針數組（一維）追蹤元素，元素本身可離散分佈。優勢：

• 保留數組 O(1) 下標隨機訪問；
• 有序時可二分查找 O(log n)；
• 插入/刪除無需移動元素，僅修改指針數組。

典型應用：內存池管理（指針指向各塊內存首址）、散列鏈表（指針指向含 next 域的節點）。

模擬指鈈與並查集

用數組下標模擬指針，節點包含 data 與 link（下標）。核心應用：並查集。

等價類與並查集操作

• Find：判斷兩元素是否同屬一類（找根節點）；
• Union：合併兩類（連接根節點）。

優化策略

• 按秩合併：將矮樹掛到高樹根下；
• 路徑壓縮：Find 過程中將沿途節點直接掛到根節點。

兩者結合使時間復雜度趨近 O(α(n))，極其高效。