0203. 移除链表元素【简单】
1. 📝 题目描述
给你一个链表的头节点 head 和一个整数 val,请你删除链表中所有满足 Node.val == val 的节点,并返回新的头节点。
示例 1:

输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]1
2
2
示例 2:
输入:head = [], val = 1
输出:[]1
2
2
示例 3:
输入:head = [7,7,7,7], val = 7
输出:[]1
2
2
提示:
- 列表中的节点数目在范围
[0, 10^4]内 1 <= Node.val <= 500 <= val <= 50
2. 🎯 s.1 - 遍历
js
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var removeElements = function (head, val) {
// 创建虚拟头节点,简化边界处理
const dummy = new ListNode(0)
dummy.next = head
let prev = dummy
let current = head
while (current !== null) {
if (current.val === val) {
// 移除当前节点
prev.next = current.next
} else {
// 移动 prev 指针
prev = current
}
current = current.next
}
return dummy.next
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
- 时间复杂度:
,其中 n 是链表长度,需要遍历整个链表 - 空间复杂度:
,只使用了常数级别的额外空间
算法思路:
- 使用哨兵节点避免处理头节点删除的特殊情况
- 遍历链表,如果下一个节点值等于 val,则跳过该节点;否则移动指针
- 返回哨兵节点的 next
3. 🎯 s.2 - 递归
js
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var removeElements = function (head, val) {
if (head === null) return head
head.next = removeElements(head.next, val)
return head.val === val ? head.next : head
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
- 时间复杂度:
,其中 n 是链表长度,需要递归访问每个节点 - 空间复杂度:
,递归调用栈的深度最多为 n
算法思路:
- 递归处理链表的下一个节点
- 如果当前节点值等于 val,返回下一个节点(删除当前节点)
- 否则返回当前节点(保留当前节点)