203. 移除链表元素
题目描述
输入链表头节点 head 和整数 val。删掉链表中所有值等于 val 的节点。
返回删除后链表的头节点；若所有节点都被删掉或链表本来为空，返回 null。
链表以数组形式表示，例如 [1,2,3]。
示例 1
输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
解释：两个值为 6 的节点被删除。
示例 2
输入：head = [], val = 1 输出：[]
解释：链表本来就是空的。
示例 3
输入：head = [7,7,7,7], val = 7 输出：[]
解释：所有节点的值都是 7，全部删掉后链表为空。
数据范围
- 节点数在
[0, 10^4]范围内。 1 <= Node.val <= 500 <= val <= 50
解题思路：哑结点 + 迭代
删除一个节点要改它前驱的 next，所以指针 prev 始终停在“待检查节点的前一个”。头节点也可能被删，于是在最前面放一个哑节点 dummy，让每个真实节点都有前驱。prev.next 的值等于 val 就跳过它（prev 不动，因为新接上来的节点还没检查）；否则 prev 前进。
为什么正确
dummy 到 prev 这一段已经不含 val；prev.next 是下一个待检查的节点。
复杂度分析
时间 O(n)，额外空间 O(1)。
易错点
删除后不要让 prev 前进：新接上来的 prev.next 可能也等于 val（连续相同值）。另外不用哑节点时，要单独处理头部连续被删的情况。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
prev = dummy
while prev.next:
if prev.next.val == val:
prev.next = prev.next.next
else:
prev = prev.next
return dummy.nextclass Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(0, head);
ListNode prev = dummy;
while (prev.next != null) {
if (prev.next.val == val) {
prev.next = prev.next.next;
} else {
prev = prev.next;
}
}
return dummy.next;
}
}class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummy = new ListNode(0, head);
ListNode* prev = dummy;
while (prev->next) {
if (prev->next->val == val) {
prev->next = prev->next->next;
} else {
prev = prev->next;
}
}
return dummy->next;
}
};func removeElements(head *ListNode, val int) *ListNode {
dummy := &ListNode{Val: 0, Next: head}
prev := dummy
for prev.Next != nil {
if prev.Next.Val == val {
prev.Next = prev.Next.Next
} else {
prev = prev.Next
}
}
return dummy.Next
}var removeElements = function(head, val) {
const dummy = new ListNode(0, head);
let prev = dummy;
while (prev.next) {
if (prev.next.val === val) {
prev.next = prev.next.next;
} else {
prev = prev.next;
}
}
return dummy.next;
};function removeElements(head: ListNode | null, val: number): ListNode | null {
const dummy = new ListNode(0, head);
let prev = dummy;
while (prev.next) {
if (prev.next.val === val) {
prev.next = prev.next.next;
} else {
prev = prev.next;
}
}
return dummy.next;
}其他解法
递归利用子问题“删除剩余链表”从后往前处理；迭代用哑结点统一头结点的情况、从前往后删除，空间 O(1)。
解法 2：递归 时间 O(n)，空间 O(n)
先递归删除 head.next 之后链表中的目标值，把结果接回 head.next。然后判断 head 本身：等于 val 就返回 head.next，否则返回 head。空链表直接返回空。
不需要哑结点，头结点和其他结点的处理方式一致，代码很短。递归深度等于链表长度，需要 O(n) 栈空间。
from typing import Optional
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
if head is None:
return None
head.next = self.removeElements(head.next, val)
return head.next if head.val == val else headclass Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null) return null;
head.next = removeElements(head.next, val);
return head.val == val ? head.next : head;
}
}class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if (!head) return nullptr;
head->next = removeElements(head->next, val);
return head->val == val ? head->next : head;
}
};func removeElements(head *ListNode, val int) *ListNode {
if head == nil {
return nil
}
head.Next = removeElements(head.Next, val)
if head.Val == val {
return head.Next
}
return head
}var removeElements = function(head, val) {
if (!head) return null;
head.next = removeElements(head.next, val);
return head.val === val ? head.next : head;
};function removeElements(head: ListNode | null, val: number): ListNode | null {
if (!head) return null;
head.next = removeElements(head.next, val);
return head.val === val ? head.next : head;
};