东莞网站优化排名网站,免费域名注册解析,沧州网站优化,搜狗广告联盟总结#xff0c;删除链表节点问题使用到列表#xff0c;哈希表#xff0c;递归比较容易超时#xff0c;我觉得使用计数排序比较稳#xff0c;处理起来也不是很难。 1. 力扣3217#xff1a;从链表中移除在数组中的节点
1.1 题目#xff1a;
给你一个整数数组 nums 和一… 总结删除链表节点问题使用到列表哈希表递归比较容易超时我觉得使用计数排序比较稳处理起来也不是很难。 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[max1];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];ListInteger 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 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;}
}
