本文學習目標或者鞏固的知識點
-
學習如何刪除鏈表中的某個節點
- 如何刪除val=k的節點
- 如何刪除倒數第n個節點
-
學習如何刪除鏈表中的某些節點
- 涉及頭節點問題如何解決
提前説明：算法題目來自力扣、牛客等等途徑
🟢表示簡單
🟡表示中等
🔴表示困難
🤮表示噁心
237. 刪除鏈表中的節點🟡🟢
有一個單鏈表的 head，我們想刪除它其中的一個節點 node。
給你一個需要刪除的節點 node 。你將 無法訪問 第一個節點 head。
鏈表的所有值都是 唯一的，並且保證給定的節點 node 不是鏈表中的最後一個節點。
刪除給定的節點。注意，刪除節點並不是指從內存中刪除它。這裏的意思是：
- 給定節點的值不應該存在於鏈表中。
- 鏈表中的節點數應該減少 1。
- node 前面的所有值順序相同。
- node 後面的所有值順序相同。
示例 1：
輸入：head = [4,5,1,9], node = 5
輸出：[4,1,9]
解釋：指定鏈表中值為 5 的第二個節點，那麼在調用了你的函數之後，該鏈表應變為 4 -> 1 -> 9通過題目可知
- 我們想刪除它其中的一個節點 node，且入參就是node（我們知道node）
- 無法訪問 第一個節點 head
- 鏈表的所有值都是唯一的
-
節點 node 不是鏈表中的最後一個節點（我們可以拿到node.next）
題解
超級簡單，不多説
class Solution {
public void deleteNode(ListNode node) {
ListNode nextNode = node.next;
node.val = nextNode.val;
node.next = nextNode.next;
}
}圖解
83. 刪除排序鏈表中的重複元素🟢
給定一個已排序的鏈表的頭 head ， 刪除所有重複的元素，使每個元素只出現一次 。返回 已排序的鏈表 。
示例 1：
輸入：head = [1,1,2]
輸出：[1,2]通過題目可知
- 已排序的鏈表（重複的節點肯定相鄰）
-
如果有重複元素，使每個元素只出現一次即可（不用考慮頭節點問題）
題解
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while(cur!=null && cur.next!=null){
//剔除重複元素 直到不符合
while(cur!=null && cur.next!=null && cur.val == cur.next.val){
cur.next = cur.next.next;
}
//下一個
cur = cur.next;
}
return head;
}圖解
- cur.val == cur.next.val 即 1=1的時候進入內循環
- cur.next = cur.next.next; cur後移
- cur = cur.next; 當cur.val != cur.next.val的時候執行cur後移
82. 刪除排序鏈表中的重複元素 II🟡
給定一個已排序的鏈表的頭 head ， 刪除原始鏈表中所有重複數字的節點，只留下不同的數字 。返回 已排序的鏈表 。
示例 1：
輸入：head = [1,2,3,3,4,4,5]
輸出：[1,2,5]通過題目可知
- 已排序的鏈表（重複的節點肯定相鄰）
-
如果有重複元素，刪除所有重複的元素（需要考慮頭節點問題）
題解
public ListNode deleteDuplicates(ListNode head) {
ListNode preHead = new ListNode(-1);
preHead.next = head;
ListNode cur = preHead;
while(cur.next!=null && cur.next.next!=null){
ListNode nextNode = cur.next;
ListNode nextNextNode = cur.next.next;
//不相等
if(nextNode.val != nextNextNode.val){
cur = cur.next;
continue;
}
//相等
while(nextNextNode!= null && nextNode.val == nextNextNode.val){
nextNextNode = nextNextNode.next;
}
cur.next = nextNextNode;
}
return preHead.next;
}圖示
19. 刪除鏈表的倒數第 N 個結點🟡
給你一個鏈表，刪除鏈表的倒數第 n 個結點，並且返回鏈表的頭結點。
示例 1：
輸入：head = [1,2,3,4,5], n = 2
輸出：[1,2,3,5]通過題目可知
- 我們需要刪除鏈表的倒數第n 個結點（如何尋找這個結點？快慢指針）
-
返回鏈表的頭結點（沒特殊説明，説明可能刪除頭節點，需要考慮頭節點問題）
題解
當涉及快慢指針的問題最好打點關鍵的日誌，方法跟蹤問題。
此題為經典的快慢指針問題。
快指針先走N步，然後快慢指針一起走，直到快指針走完鏈表為null。一般慢指針就是要刪除的節點。找到刪除的節點或者要刪除的前一個節點的話就容易多了。
public ListNode removeNthFromEnd(ListNode head, int n) {
//由於可能刪除頭節點 所以設置虛擬節點preHead
ListNode preHead = new ListNode(-1);
preHead.next = head;
//設置快指針 從preHead開始
ListNode fast = preHead;
//先走N+1步
for(int i=0; i<=n; i++){
fast = fast.next;
}
//【調試】
System.out.println("fast="+(fast==null?"null":fast.val));
//快慢指針同步走
ListNode slow = preHead;
while(fast != null){
slow = slow.next;
fast = fast.next;
}
//【調試】
System.out.println("slow="+(slow==null?"null":slow.val));
//跳過要刪除的點
slow.next = slow.next.next;
return preHead.next;
}