【数据结构与算法 | 灵神题单 | 删除链表篇】力扣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 <= 105
• 1 <= nums[i] <= 105
• nums 中的所有元素都是唯一的。
• 链表中的节点数在 [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到100int[] 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;}}// 此时整个链表都要被删除，所以返回nullif(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 <= 104
• 1 <= a <= b < list1.length - 1
• 1 <= 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;}
}