删除链表结点
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指针用于得到待删结点的后继，通过两工作指针就能解决链表删除问题。
此外，如果头结点可能被删除，那就要构造一个虚拟头结点，方便删除头结点。
