网站建设手机端官网/百度app官网下载安装

一、需求

• 删除链表中等于给定值 val 的所有节点。

示例:

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

二、递归法

2.1  思路分析

1. 思路类似于删除链表中的节点：https://blog.csdn.net/Sruggle/article/details/113835270；
2. 方法的作用是返回不含给定元素的链表，对于链表中与给定元素相同的元素，我们跳过它，不同的元素，我们连接它；

2.2  代码实现

class Solution {public ListNode removeElements(ListNode head, int val) {if(head == null) {return null;}if(head.next == null && head.val == val) {return null;}if(head.val == val) {return removeElements(head.next, val);} else {head.next = removeElements(head.next, val);}return head;}
}

2.3  复杂度分析

• 时间复杂度为O(N)；
• 空间复杂度为O(N)；

三、哨兵节点

3.1  思路分析

1. 对链表加入伪头节点，这利用双指针，若遇到待删除的元素，则直接连接其后的元素，若不是待删除的元素，那么让它成为被删除节点的前一个节点，直到判断为所有的节点；

3.2  代码实现

class Solution {public ListNode removeElements(ListNode head, int val) {ListNode sentinel = new ListNode(0);sentinel.next = head;ListNode pre = sentinel;ListNode cur = head;while(cur != null) {if(cur.val == val) {pre.next = cur.next;} else {pre = cur;}cur = cur.next;}return sentinel.next;}
}

3.3  复杂度分析

• 时间复杂度为O(N)；
• 空间复杂度为O(1)；

四、学习地址

作者：LeetCode

链接：https://leetcode-cn.com/problems/remove-linked-list-elements/solution/yi-chu-lian-biao-yuan-su-by-leetcode/