鏈表演算法題解題技巧歸納總結
- 2022 年 6 月 21 日
- 筆記
最近集中刷了一批鏈表的題型，在這裡總結一下解題技巧，以及對應題目的解題思路。
解題思路並不會細緻入微，主要是為了總結歸類，並且希望用幾句話來激發靈感，權當是沒思路時的指引以及以後複習時的提綱了。
還有一些重要或者總會繞暈的經典題目，也在這裡記錄一下程式碼的實現邏輯。
一、解決鏈表題型的兩個技巧
遇到鏈表相關的題，無論問題是什麼，先要想想是不是可以用上以下的兩個技巧。
- 哨兵節點
- 雙指針
1、哨兵節點
哨兵節點是一個非常常用的鏈表技巧，在處理鏈表邊界問題的場景下，可以減少我們程式碼的複雜度。主要解決的問題如下：
- 處理完一條鏈表後，需要返回這個鏈表的頭結點。我們在一開始的時候使用哨兵節點（dummy），讓它的 next 節點指向 head 節點。最後 return 時直接返回 dummy.next 即可。
- 在對鏈表進行插入或刪除節點時，使用哨兵節點可以簡化刪除 head 節點或者向 head 前插入節點時的處理邏輯。
- 在某些遍歷鏈表的時候，可能會需要同時記錄 pre 節點。當你從 head 節點開始遍歷時，head 是沒有 pre 節點的（為null）。而此時引用哨兵節點，相當於幫助 head 節點初始化了一個 pre 節點，可以方便的解決 pre 節點為空的問題。
因為哨兵節點使用場景很廣泛，所以在這裡就不針對性的列出典型題目了。
2、雙指針
雙指針實在是太好用了，其實不止是鏈表，對於數組題來說，也是非常好用的技巧。
雙指針的主要用法有以下幾種：
- 兩個指針在兩條鏈表上行走
- 快慢指針，同時前進
- 前後指針，前指針先走 n 步，之後兩個指針同時前進
兩個指針在兩條鏈表上行走
有時，你需要將兩條鏈表合併成一條鏈表，或者要將一條鏈表拆分成兩條鏈表。此時，需要用兩個指針分別在兩條鏈表上行走，並處理邏輯。
典型題目：
-
21. 合併兩個有序鏈表：兩個指針在兩條鏈表上行走，哪個指針指向的節點值大，則將該節點放到合併後的鏈表上，指針繼續向前一步。
-
86. 分隔鏈表：根據指定的目標值，將一個鏈表先分割成兩個鏈表。因此，需要兩個指針在分割出來的兩個鏈表上行走。之後再將兩個鏈表直接頭尾合併。
-
160. 相交鏈表：兩個指針在兩條鏈表上行走，當一個指針指向當前列表的結尾時，繼續遍歷另外一個鏈表。這樣可以保證兩個指針指向相同的節點時，這個節點就是相交節點。
快慢指針
快指針的速度是慢指針 n 倍，則當快指針走完時，慢指針停留的地方就是整個鏈表的 1/n 處（大概位置）。一般情況下都是慢指針走一步，快指針走兩步。
典型題目：
-
876. 鏈表的中間結點：快指針走兩步，慢指針走一步。快指針走到結尾時，則慢指針在中間位置。
-
141. 環形鏈表：快指針走兩步，慢指針走一步。當快慢指針相遇時，從頭結點再出發一個慢指針，兩個慢指針一起走，再次相遇時，則是環的入口。
-
234. 迴文鏈表：實際上也是找到鏈表的中間位置，然後去判斷是否為迴文。判斷迴文的邏輯，藉助棧或者反轉後半段鏈表都可以。
-
148. 排序鏈表：在使用歸併排序時，也是通過快慢指針找到每個子鏈表的中間節點，去歸併處理。
一個指針先走 n 步
因為沒有辦法獲取鏈表的長度，對於尋找倒數第 n 個節點的問題時，這種方法可以一次遍歷找到目標節點。
典型題目：
-
19. 刪除鏈表的倒數第 N 個結點：一個指針先走 n 步，然後兩個指針同時前進，當先出髮指針遍歷完成時，後出髮指針就在倒數第 n 個節點。
-
61. 旋轉鏈表：與上一題類似，只是先走的 n 步可能會超過鏈表的總長度，需要取模處理一下。
二、經典鏈表題的解法
反轉鏈表
206. 反轉鏈表 是最經典的鏈表題了。除了進階題 92. 反轉鏈表 II，反轉鏈表也會用於其他鏈表題型的解答中，比如上文所說的 234. 迴文鏈表。
反轉鏈表主要有遞歸法和迭代法兩種解決方法，因為指針指來指去的容易暈頭轉向，所以在這裡記錄標準的解答程式碼。
遞歸法
public ListNode reverseList(ListNode head) {
// 這個head就是原鏈表的最後一個節點，也是反轉後鏈表的新節點
if (head == null || head.next == null) {
return head;
}
// 本質上，resultNode就是遞歸到最深處後，一層層返回的新鏈表的頭結點
ListNode resultNode = reverseList(head.next);
head.next.next = head;
head.next = null;
return resultNode;
}
迭代法
public ListNode reverseList(ListNode head) {
ListNode current = head;
ListNode pre = null;
ListNode next;
while (current != null) {
next = current.next;
current.next = pre;
pre = current;
current = next;
}
return pre;
}
LRU快取
146. LRU 快取 畢竟是個快取，肯定是鍵值對的結構，所以要用到HashMap。
而在讀寫方面，快取是有要求的：函數 get 和 put 必須以 O(1) 的平均時間複雜度運行。
為了達成這個要求，底層的數據結構需要用鏈表來實現。
所以我們實現的 LRU 底層的數據結構是：HashMap +鏈表。
程式碼如下，雖然不夠優雅，但是方便理解邏輯。
public class LRUCache {
private int maxSize = 0;
private Node head = new Node();
private Node tail = head;
HashMap<Integer, Node> map = new HashMap<>();
public LRUCache(int capacity) {
this.maxSize = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (map.containsKey(key)) {
Node node = map.get(key);
// get也是使用了該值，因此需要將該值更新到最近使用的位置
updateNode(node);
return node.value;
}
return -1;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Node node = map.get(key);
node.value = value;
updateNode(node);
return;
}
// 新插入的值放到鏈尾
Node node = new Node(key, value);
node.prev = tail;
map.put(key, node);
tail.next = node;
tail = node;
if (map.size() > maxSize) {
// 此時需要移除最久未使用數據值
Node removed = head.next;
head.next = removed.next;
head.next.prev = head;
map.remove(removed.key);
}
}
private void updateNode(Node current) {
// 如果當前節點已經是尾節點，則不需要移動
if (current.next == null) {
return;
}
// 當前節點的前節點指向當前節點的後節點，即原鏈表中刪除該節點
current.prev.next = current.next;
current.next.prev = current.prev;
// 當前節點放到尾節點
current.prev = tail;
current.next = null;
tail.next = current;
// 尾節點移動
tail = current;
}
class Node {
public int key;
public int value;
public Node prev;
public Node next;
public Node(){}
public Node(int key,int value) {
this.key = key;
this.value = value;
}
}
}
