冲击大厂算法面试=>链表专题【链表删除】

本文学习目标或者巩固的知识点

• 学习如何删除链表中的某个节点
  • 如何删除val=k的节点
  • 如何删除倒数第n个节点
• 学习如何删除链表中的某些节点
  • 涉及头节点问题如何解决

提前说明：算法题目来自力扣、牛客等等途径

🟢表示简单
🟡表示中等
🔴表示困难
🤮表示恶心

237. 删除链表中的节点🟡🟢

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9

通过题目可知

1. 我们想删除它其中的一个节点 node，且入参就是node**（我们知道node）**
2. 无法访问 第一个节点 head
3. 链表的所有值都是****唯一的
4. 节点 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,1,2]
输出：[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,2,3,3,4,4,5]
输出：[1,2,5]

通过题目可知

1. 已排序的链表（重复的节点肯定相邻）
2. 如果有重复元素，删除所有重复的元素**（需要考虑头节点问题）**

题解

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 个结点🟡

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

通过题目可知

1. 我们需要删除链表的倒数第n 个结点（如何寻找这个结点？快慢指针）
2. 返回链表的头结点**（没特殊说明，说明可能删除头节点，需要考虑头节点问题）**

题解

当涉及快慢指针的问题最好打点关键的日志，方法跟踪问题。

此题为经典的快慢指针问题。

快指针先走N步，然后快慢指针一起走，直到快指针走完链表为null。一般慢指针就是要删除的节点。找到删除的节点或者要删除的前一个节点的话就容易多了。

public ListNode removeNthFromEnd(ListNode head, int n) {//由于可能删除头节点 所以设置虚拟节点preHeadListNode 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;
}