【算法训练-链表四】【删除】：删除链表的倒数第N个节点、删除有序链表中的重复元素、删除有序链表中的重复元素II

废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【删除有序链表中的重复元素】，使用【链表】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。

在这里插入图片描述

名曲目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。

删除链表的倒数第N个节点【MID】

来解决这道MID题目

题干

直接粘题干和用例

输入：
{1,2},2    返回值：
{2}

解题思路

给出解题思路
在这里插入图片描述
算法实现步骤如下：

fast快指针先行N步和慢指针拉开N个节点距离
fast和slow指针一直向前直到快指针到链表的尾节点停止，此时慢指针因为落后快指针N个节点，所以在链表的倒数第N+1个位置
slow指针直接指向其下一个节点的下一个，将下一个节点从链表中删除

注意这里为什么用了虚拟头结点作为哨兵，如果要删除的是倒数第5个节点也就是头节点，按照上述算法将无法处理，所以需要设置一个虚拟头节点

代码实现

给出代码实现基本档案

基本数据结构：链表
辅助数据结构：无
算法：迭代
技巧：双指针

其中数据结构、算法和技巧分别来自：

10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
技巧：双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;*   public ListNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param head ListNode类* @param n int整型* @return ListNode类*/public ListNode removeNthFromEnd (ListNode head, int n) {// 1 入参校验及哨兵节点设置if (head == null) {return null;}ListNode dummyNode = new ListNode(-1);dummyNode.next = head;// 2 定义快慢指针，都从表头出发ListNode fast = dummyNode;ListNode slow = dummyNode;// 3 快指针先行N步，拉开与慢指针N个节点间隔while (n > 0) {fast = fast.next;n--;}// 4 快慢指针同时前进，当快指针到链表尾部的时候，慢指针就对应倒数第N个节点的前一个节点，因为快慢指针拉开的是N个节点距离while (fast.next != null) {fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return dummyNode.next;}}

复杂度分析

时间复杂度：由于只遍历了一遍，所以时间复杂度为O（N）
空间复杂度：由于没有用到辅助空间，所以空间复杂度为O（1）

删除有序链表中的重复元素【EASY】

先来个简单的热热身

题干

直接粘题干和用例

解题思路

比较简单，由于链表有序，则重复元素一定相邻，删除重复元素即可。
在这里插入图片描述

代码实现

给出代码实现基本档案

基本数据结构：链表
辅助数据结构：无
算法：迭代
技巧：无

其中数据结构、算法和技巧分别来自：

10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
技巧：双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;*   public ListNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param head ListNode类* @return ListNode类*/public ListNode deleteDuplicates (ListNode head) {// 1-单指针进行链表遍历ListNode cur = head;while (cur != null && cur.next != null) {// 2-只有当前节点和下一节点都不为null才能进行val比较if (cur.val == cur.next.val) {// 2-1 比较一致则删除下一个节点cur.next = cur.next.next;} else {// 2-2 比较不一致则继续向前搜索，直到cur到链表尾部cur = cur.next;}}return head;}
}

复杂度分析

时空复杂度分析

时间复杂度：遍历一遍链表，所以时间复杂度O（N）
空间复杂度：未用到辅助结构，所以空间复杂度O（1）

删除有序链表中的重复元素II【MID】

难度升级，和上一题的区别是把重复的元素全部干掉而不是留一个，所以需要有pre指针记录重复节点的上一个

题干

直接粘题干和用例

解题思路

给出解题思路，最好有图
这里需要注意虽有有两个while，但是内层的while是去重用的，它前进的时候也会影响到外层循环，所以总体时间复杂度就不是O(N^2)，而是O(N)

代码实现

给出代码实现基本档案

基本数据结构：链表
辅助数据结构：无
算法：迭代
技巧：双指针

其中数据结构、算法和技巧分别来自：

10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
技巧：双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;*   public ListNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param head ListNode类* @return ListNode类*/public ListNode deleteDuplicates (ListNode head) {// 1 入参校验if (head == null || head.next == null) {return head;}// 2 设置哨兵节点ListNode dummy = new ListNode(-1);dummy.next = head;ListNode pre = dummy;ListNode cur = head;// 3 双指针遍历while (cur != null && cur.next != null) {if (cur.val != cur.next.val) {// 1-比较不一致则继续前进cur = cur.next;pre = pre.next;} else {// 2-比较一致则cur继续向前直到直到不一致的为止while ( cur != null && cur.next != null && cur.val == cur.next.val) {cur = cur.next;}// 3-删除中间所有的重复节点，cur继续指向新节点pre.next = cur.next;cur = cur.next;}}return dummy.next;}
}