【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82， 237
总结，删除链表节点问题使用到列表，哈希表，递归比较容易超时，我觉得使用计数排序比较稳，处理起来也不是很难。
1. 力扣3217：从链表中移除在数组中的节点
1.1 题目：
给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后，返回修改后的链表的头节点。
示例 1：
输入： nums = [1,2,3], head = [1,2,3,4,5]
输出： [4,5]
解释：
移除数值为 1, 2 和 3 的节点。
示例 2：
输入： nums = [1], head = [1,2,1,2,1,2]
输出： [2,2,2]
解释：
移除数值为 1 的节点。
示例 3：
输入： nums = [5], head = [1,2,3,4]
输出： [1,2,3,4]
解释：
链表中不存在值为 5 的节点。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 105nums中的所有元素都是唯一的。- 链表中的节点数在
[1, 105]的范围内。 1 <= Node.val <= 105- 输入保证链表中至少有一个值没有在
nums中出现过。
1.2 思路：
感觉蛮容易超时的，我用了列表 / 哈希表 / 递归三种方法都超时了，然后想到用计数排序空间换时间，跑起来以后感觉效率还蛮高的。
1.3 题解：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
// 使用列表和哈希表和递归全超时了，只能迫不得已使用计数排序了
public ListNode modifiedList(int[] nums, ListNode head) {
// max方法找到nums数组的最大值
int max = max(nums);
// 以空间换时间
int[] temp = new int[max+1];
for(int i : nums){
temp[i]++;
}
// 哨兵节点
ListNode dummy = new ListNode(0);
// 测试目标节点的下一个节点需不需要删除
ListNode p = dummy;
dummy.next = head;
while(p.next != null){
//如果下一个节点的值大于max，肯定没出现在nums数组中
if(p.next.val <= max && temp[p.next.val] != 0){
p.next = p.next.next;
}else{
p = p.next;
}
}
// 返回哨兵节点的下一个节点即可。
return dummy.next;
}
private static int max(int[] nums){
int max = Integer.MIN_VALUE;
for(int i : nums){
if(max < i){
max = i;
}
}
return max;
}
}
2. 力扣82：删除排序链表中的重复元素2
2.1 题目：
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例 1：
输入：head = [1,2,3,3,4,4,5] 输出：[1,2,5]
示例 2：
输入：head = [1,1,1,2,3] 输出：[2,3]
提示：
- 链表中节点数目在范围
[0, 300]内 -100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
2.2 思路：
由于节点的值的范围就在-100到100，很容易想到计数排序，用空间换时间。
只是最后还要考虑p的父节点为空的情况，是在链表节点值的个数全在两个以上，导致整个链表都要被删除，所以pparent为null返回null。
2.3 题解：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
// 继续使用计数排序
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 因为链表的节点的值的范围是-100到100
int[] temp = new int[201];
List<Integer> list = new ArrayList<>();
ListNode p = head;
while(p != null){
temp[p.val + 100]++;
list.add(p.val);
p = p.next;
}
p = head;
ListNode pparent = null;
for(int i : list){
if(temp[i + 100] == 1){
p.val = i;
pparent = p;
p = p.next;
}
}
// 此时整个链表都要被删除，所以返回null
if(pparent == null){
return null;
}
pparent.next = null;
return head;
}
}
3. 力扣1669：合并两个链表
3.1 题目：
给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。
请你将 list1 中下标从 a 到 b 的全部节点都删除，并将list2 接在被删除节点的位置。
下图中蓝色边和节点展示了操作后的结果：
请你返回结果链表的头指针。
示例 1：
输入：list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002] 输出：[10,1,13,1000000,1000001,1000002,5] 解释：我们删除 list1 中下标为 3 和 4 的两个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。
示例 2：
输入：list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004] 输出：[0,1,1000000,1000001,1000002,1000003,1000004,6] 解释：上图中蓝色的边和节点为答案链表。
提示：
3 <= list1.length <= 1041 <= a <= b < list1.length - 11 <= list2.length <= 104
3.2 思路：
理清关系还是蛮简单的，没什么难度。
3.3 题解：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
// 找到list1链表的a的前一个位置，b的后一个位置
int index_a = a - 1;
int index_b = b + 1;
int k = 0;
ListNode list1_a = null;
ListNode list2_b = null;
ListNode p = list1;
while(p != null) {
if(k == index_a){
list1_a = p;
}
if(k == index_b){
list2_b = p;
break;
}
k++;
p = p.next;
}
// 再找到list2链表的尾节点即可
p = list2;
while(p.next != null){
p = p.next;
}
// 此时p为位于最后一个节点的位置
//处理一下各个节点的人际关系即可。
list1_a.next = list2;
p.next = list2_b;
// 1 <= a <= b < list1.length - 1
// 头节点是不会被删除的
return list1;
}
}