刪除鏈表結點類問題
刪除鏈表結點
NO1. 刪除鏈表倒數第 k個結點
給定一個鏈表，刪除鏈表的倒數第 n 個節點並返回鏈表的頭指針。要求：空間複雜度 \(O(1)\)，時間複雜度 \(O(n)\)
如果倒數第 k 個結點剛好是頭結點，那頭結點需要特殊處理。為了各個結點能等同操作，設置一個虛擬頭結點。
尋找倒數第 k 個結點常使用「快慢雙指針」來實現。
演算法流程：
- step 1 ：在原頭結點前面添加一個虛擬頭結點；
- step 2 ：使用快慢指針找到倒數第 k+1 個結點（有了前驅結點，第 k 個結點才能刪掉）；
- step 3 ：刪除倒數第 k 個結點，返回頭結點；
程式碼實現：
public class Solution {
static class ListNode {
int val;
ListNode next = null;
}
public ListNode removeNthFromEnd (ListNode head, int k) {
// 1. 添加一個虛擬頭結點
ListNode dummy = new ListNode(-1);
dummy.next = head;
// 2. 使用快慢指針找到倒數第 k+1 個結點
ListNode prev = getNode(dummy, n);
// 3. 刪除 倒數 第 k 個結點
prev.next = prev.next.next;
return dummy.next;
}
// 找到倒數第 k+1 個結點
public ListNode getNode(ListNode newHead, int k) {
ListNode slow = newHead, fast = newHead;
for(int i = 0; i <= k; i++) fast = fast.next;
while(fast != null) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
複雜度分析：
- 時間複雜度：\(O(n)\)，其中 \(n\) 為鏈表長度；
- 空間複雜度：\(O(1)\)，無額外輔助空間使用；
NO2. 刪除有序鏈表中重複元素Ⅰ
刪除給出鏈表中的重複元素（鏈表中元素從小到大有序），使鏈表中的所有元素都只出現一次。例如：給出的鏈表為1→1→2→3→3，返回1→2→3。
進階：空間複雜度 O(1)，時間複雜度O(n)
對於重複元素，僅保留第一個，後面重複地直接跳過。
演算法流程：
- step 1 ：特殊情況判斷（空鏈表或僅有一個結點的鏈表）；
- step 2 ：使用兩個工作指針，一個指向重複元素的第一個結點（若存在），另一個往後遍歷去重；
每輪循環結束時 prev 始終都是 cur 的前驅。
程式碼實現：
public class Solution {
static class ListNode {
int val;
ListNode next = null;
}
public ListNode deleteDuplicates (ListNode head) {
if(head == null || head.next == null) return head;
ListNode cur = head.next, prev = head;
while(cur != null) {
// 元素重複，要刪掉 cur
if(prev.val == cur.val) {
prev.next = cur.next;
} else {
// 沒重複的 prev 了，prev 指向 cur，對下一個值進行去重
prev = cur;
}
cur = cur.next;
}
}
}
複雜度分析：
- 時間複雜度：\(O(n)\)，其中 \(n\) 為鏈表長度；
- 空間複雜度：\(O(1)\)，無額外輔助空間使用；
NO3. 刪除有序鏈表中重複元素Ⅱ
跟上一題的區別就在於，上一題的所有元素都至少會保留一個，而本題中只要有重複，重複結點一個也不保留。
例如：1→2→3→3→4→4→5，返回1→2→5.
本題跟上題不同，如果頭結點重複了，那頭結點就得刪除，為了方便操作，添加一個虛擬頭結點。
演算法流程：
-
step 1 ：特殊情況判斷（空鏈表或僅有一個結點的鏈表）；
-
step 2 ：添加一個虛擬頭結點，為了方便刪除第一個結點；
-
step 3 ：還是利用兩個工作指針，每次就比較相鄰兩個元素是否相等，
- 相等的話就跳過所有重複結點（一個不留）；
- 不相等，prev 指針後移，去判斷 prev 下一個元素是否有重複；
-
step 4 ：返回虛擬頭結點的 next；
程式碼實現：
public ListNode deleteDuplicates (ListNode head) {
// 口 -> 1 -> 1 -> 2 -> 3 -> 3
if(head == null || head.next == null) return head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy, cur = dummy.next;
while(cur != null && cur.next != null) {
if(cur.val == cur.next.val) {
// 相鄰元素相等，跳過
while(cur.next != null && cur.val == cur.next.val) {
cur = cur.next;
}
// 上面while結束，cur指向有重複的最後一個元素，這一步實現跳過所有重複結點
prev.next = cur.next;
} else {
// 相鄰元素不相等，prev指針後移，指向cur
prev = cur;
}
cur = cur.next;
}
return dummy.next;
}
複雜度分析：
- 時間複雜度：\(O(n)\)，其中 \(n\) 為鏈表長度；
- 空間複雜度：\(O(1)\)，無額外輔助空間使用；
小結
刪除鏈表類問題，通常使用雙指針來操作，prev指針來得到待刪結點的前驅，cur指針用於得到待刪結點的後繼，通過兩工作指針就能解決鏈表刪除問題。
此外，如果頭結點可能被刪除，那就要構造一個虛擬頭結點，方便刪除頭結點。
