网站国际互联网备案号设计培训网页班

网站国际互联网备案号,设计培训网页班,代刷网站开发,网站备案后要做什么在处理链表的删除操作时#xff0c;一般先找到待删除结点的前驱#xff0c;否则会断链。而对于没有虚拟头结点的链表#xff0c;删除第一个结点不好处理#xff0c;因为没有头结点#xff08;但不影响删除最后一个结点#xff09;#xff0c;此时就需要构造一个虚拟头结…在处理链表的删除操作时一般先找到待删除结点的前驱否则会断链。而对于没有虚拟头结点的链表删除第一个结点不好处理因为没有头结点但不影响删除最后一个结点此时就需要构造一个虚拟头结点可以更方便的完成所有可能的删除操作。题目1删除链表中所有值为val的结点如1-2-6-3-4-5-6-null要求删除值为6的结点返回1-2-3-4-5-null。公用代码​ public class ListNode { public int val; public ListNode next; public ListNode(int x) { this.val x; this.next null; } public static ListNode createList(int[] nums) { if(null nums || 0 nums.length) return null; ListNode head new ListNode(nums[0]); ListNode needle head; for(int i 1; i nums.length;i) { ListNode node new ListNode(nums[i]); needle.next node; needle needle.next; needle.next null; } return head; } }我们先给出不用虚拟头结点完成链表删除操作的过程看看具体繁琐在哪// 203 没有虚拟头结点的情况下需要下面的判断才能处理val等于头结点的情况 public ListNode removeElements(ListNode head, int val) { // 循环处理头结点有多个与头结点值相同的结点且删除的就是它们 while (head ! null head.val val) { // head一直在变换 head head.next; } // 在进行下面的while循环之前判断一下 if (head null) return null; // 下面的逻辑是删除非头结点删除头结点在上面已经处理了 ListNode pre head; while (pre.next ! null) { // 找到了要删除的结点 if (pre.next.val val) pre.next pre.next.next; else // 没有找到直接移动指针遍历下一个结点即可 pre pre.next; } return head; }上面的处理需要单独处理头结点下面这段程序是通过添加了一个虚拟头结点来避免这种情况。// 203 添加了虚拟头结点更简单且便于理解 public ListNode removeElements1(ListNode head, int val) { // 创建一个虚拟头结点这样不用单独处理头结点 ListNode dummyHead new ListNode(-1); dummyHead.next head; ListNode pre dummyHead; // 从实际的头结点开始遍历但是保证了实际的头结点具有自己的前驱 while (pre.next ! null) { // 找到了要删除的结点 if (pre.next.val val) pre.next pre.next.next; else// 没找到了要删除的结点直接遍历下一个结点 pre pre.next; } // 一定注意dummyHead指向一只未变化变化的是临时指针pre return dummyHead.next; }题目2给定一个有序链表将其中有重复的元素全部删除如1-2-3-3-4-4-5-null返回1-2-5再如1-1-1-2-3返回2-3。实现方式一使用检查表的方式效率较低。import java.util.ArrayList; import java.util.List; public class Solution { public ListNode deleteDuplicates(ListNode head) { if (null head) return null; ListNode pointer head; ListInteger tmpList new ArrayListInteger(); int index -1; // 记录想等元素的个数避免漏删 int equalCnt 1; while (pointer ! null) { int value pointer.val; // 临时列表中不存在就添加进去对应的索引值加1只是添加重复元素的第一个值 if (!tmpList.contains(value)) { // 尝试删除所有值等于上一个元素值的元素有则删除 if (equalCnt 1) { tmpList.remove(index--); } // 添加新的元素 tmpList.add(value); index; // 将新元素的equalCnt置为1 equalCnt 1; } else {// 临时列表中存在不添加只记录重复元素的个数以便下面的删除操作 equalCnt; // 最后一个元素与前面的元素重复的情况 if (null pointer.next) tmpList.remove(index--); } // 指针后移遍历下一个链表元素 pointer pointer.next; } // 使用虚拟头结点从新创建一个链表这种方法思路简单辅助空间大 ListNode dummyHead new ListNode(-1); ListNode cur dummyHead; for (Integer tmp : tmpList) { cur.next new ListNode((int) tmp); cur cur.next; } return dummyHead.next; } public static void main(String[] args) { int[] nums { 1, 1 }; ListNode link ListNode.createList(nums); ListNode result new Solution().deleteDuplicates(link); while (null ! result) { System.out.print(result.val ); result result.next; } } }实现方式二使用两个列表作为检查表记录元素出现的次数但是使用map不行因为map存储数据的时候会根据hash值进行排序导致乱序。例如{2,1}输出为1-2。import java.util.ArrayList; import java.util.List; class Solution { public ListNode deleteDuplicates(ListNode head) { if (null head) return head; // 定义两个list来充当检查表valus表示元素的值times表示对应值出现的次数 ListInteger values new ArrayListInteger(); ListInteger times new ArrayListInteger(); int time 1; boolean first true; while (head ! null) { int value head.val; // 第一个结点需要特殊处理 if (!values.contains(value)) { // 将上一个元素的出现次数添加到times中 if (!first) // 第一个元素出现的次数到与他值不同的元素出现时才添加 times.add(time); // 添加新元素到values中 values.add(value); // 重置time time 1; } else // 元素重复时出现次数加1 time; head head.next; first false; // 到了最后一个结点需要特殊处理来记录最后一个元素出现的次数 if (head null) times.add(time); } // 定义一个虚拟结点 ListNode dummyHead new ListNode(-1); // 定义一个穿针引线的指针让它去串连所有合法的结点头结点只指向头结点不需要移动 // 且一定将该指针与头结点建立联系否则会断链 ListNode tmpNode dummyHead; for (int i 0; i times.size(); i) { if (1 times.get(i)) { tmpNode.next new ListNode(values.get(i)); tmpNode tmpNode.next; } } return dummyHead.next; } public static void main(String[] args) { int[] nums { 1, 1, 1, 2 }; ListNode link ListNode.createList(nums); ListNode result new Solution().deleteDuplicates(link); while (null ! result) { System.out.print(result.val ); result result.next; } } }实现方式三使用双指针直接操作链表效率更高。public class LC82 { public ListNode deleteDuplicates(ListNode head) { ListNode dummyHead new ListNode(-1); dummyHead.next head; ListNode previous dummyHead; // 从头结点开始遍历因为要删除所有重复的结点要考虑前驱previous下的两个位置的结点。 while (previous.next ! null previous.next.next ! null) { if (previous.next.val previous.next.next.val) { int dupValue previous.next.val; while (previous.next ! null previous.next.val dupValue) { previous.next previous.next.next; } } else { previous previous.next; } } return dummyHead.next; } public static void main(String[] args) { int[] nums { 2, 1 }; ListNode link ListNode.createList(nums); ListNode result new LC82().deleteDuplicates(link); while (null ! result) { System.out.print(result.val ); result result.next; } } }