单链表删除相关算法总结（5种题型） |
您所在的位置：网站首页 › 单链表取值算法 › 单链表删除相关算法总结（5种题型） |
|
目录
本文介绍单链表删除相关的常见算法。 移除链表元素（力扣：203）删除链表中的节点（力扣：237）删除链表的倒数第N个节点（力扣：19）删除排序链表中的重复元素（力扣：83）删除排序链表中的重复元素 II（力扣：82） 算法实现链表节点： public class ListNode{ int val; ListNode next; ListNode(int x) { val = x; } } 1. 移除链表元素 题目删除链表中等于给定值 val 的所有节点。 分析 删除一个节点，我们首先要找到目标节点。然后，目标节点的上一个节点的next，指向目标节点的next节点，即可完成删除。然而head节点没有“上一个节点”，这时，我们需要新建一个哑节点，然后让它作为head节点的上一个节点。 哑节点哑节点（dummy node）是初始值为NULL的节点，它可以起到避免处理头节点为空的边界问题的作用，减少代码执行异常的可能性。 哑节点的使用可以对代码起到简化作用，在删除节点，或者进行有序插入时，带有头部哑节点的链表可以简化代码的逻辑，我们的代码可以不用考虑第一个节点的特殊情况。 代码实现 /** * 删除链表中等于val的所有节点 leetcode203 * @param head * @param val * @return */ public ListNode removeElements(ListNode head, int val){ ListNode pre = new ListNode(-1); pre.next = head; ListNode cur = pre; while (cur.next != null){ if (cur.next.val == val){ cur.next = cur.next.next; }else { cur = cur.next; } } return pre.next; } 2. 删除链表中的节点 题目请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。 说明: 链表至少包含两个节点。 链表中所有节点的值都是唯一的。 给定的节点为非末尾节点并且一定是链表中的一个有效节点。 不要从你的函数中返回任何结果。 分析这个题目输入参数只有一个，是将要删除的节点，所以题目可以理解为”删除指定的节点“。 删除当前节点，需要找到上一个节点，然后让上一个节点的next指向，当前节点的next节点即可。但是这是一个单链表，我们通过当前节点无法找到它的上一个节点。 所以，我们需要换个思路，将当前节点改为next节点，然后删除next节点也就变相的实现了删除当前节点了。 代码实现 /** * 删除当前节点 leetcode 19 * @param head */ public void deleteNode(ListNode head) { ListNode next = head.next; head.val = next.val; head.next = next.next; } 3. 删除链表的倒数第N个节点 题目给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 分析删除链表的倒数第N个节点，最简单的方法就是遍历链表，找到链表的长度，然后再找找倒数N个节点就非常简答了。但是这样会经过2次遍历。 我们换个思路： 使用快慢指针（双指针），让快指针先走N-1个节点，然后快慢指针一起走，当快指针指向最后一个节点时，慢指针指向了倒数第N个节点。同时，我们可以使用哑节点来处理头节点的边界问题。 代码实现 /** * 删除链表的倒数第N个节点 leetcode 19 * @param head * @param n * @return */ public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode quick = dummy; ListNode slow = dummy; for (int i = 0; i < n + 1; i++) { quick = quick.next; } while (quick != null) { quick = quick.next; slow = slow.next; } slow.next = slow.next.next; return dummy.next; } 4. 删除排序链表中的重复元素 题目给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。 分析题目中的单链表是已排序的列表，所以，从链表头开始，依次对比节点值，如果相等，则删除即可。 代码实现 /** * 83. 删除排序链表中的重复元素 * @param head * @return */ public ListNode deleteDuplicates(ListNode head) { ListNode cur = head; while (cur != null && cur.next != null){ if (cur.val == cur.next.val){ cur.next = cur.next.next; }else { cur = cur.next; } } return head; } 5. 删除排序链表中的重复元素 II 题目给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。 示例: 输入: 1->2->3->3->4->4->5 输出: 1->2->5 分析该题和上一题的区别是：要删除重复数字的所有节点。 思路1：可以使用上一题的思路，遍历整个链表，当节点中的值出现重复时，则删除重复的节点，例如节点3重复，则删除第一个之后所有重复的节点，最后删除当前节点即可。 思路2：遍历链表时，使用2个指针，第一个指针pre指向无重复节点的最右端，第二个指针cur指向当前节点，当前节点与后面节点值相等时，当前节点后移一位，直到找到不相等的值为止，这时让pre的next指向cur的next，就会把所有重复元素都删除掉了。 代码实现1 /** * 82. 删除排序链表中的重复元素 II * * @param head * @return */ public ListNode deleteDuplicates2(ListNode head) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode cur = head, pre = dummy; boolean isDel = false; while (cur != null && cur.next != null) { if (cur.val == cur.next.val) { cur.next = cur.next.next; isDel = true; } else { if (isDel) { pre.next = cur.next; cur = pre.next; isDel = false; } else { pre = cur; cur = cur.next; } } } if (isDel) { pre.next = cur.next; } return dummy.next; } 代码实现2 /** * 82. 删除排序链表中的重复元素 II * * @param head * @return */ public ListNode deleteDuplicates1(ListNode head) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode cur = dummy.next, pre = dummy; while (cur != null && cur.next != null) { if (cur.val == cur.next.val) { while (cur != null && cur.next != null && cur.val == cur.next.val) { cur = cur.next; } pre.next = cur.next; cur = pre.next; } else { pre = pre.next; cur = cur.next; } } return dummy.next; } |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |