203. 移除链表元素

已解答

简单

相关标签

相关企业

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

• 列表中的节点数目在范围 [0, 104] 内

• 1 <= Node.val <= 50

• 0 <= val <= 50

## LeetCode 203 移除链表元素（Remove Linked List Elements）

### 题目描述

删除链表中等于给定值 val 的所有节点，并返回新的头节点。

### 解题思路

1. 虚拟头节点（Dummy Node）技巧

- 为了方便处理头节点被删除的情况，创建一个虚拟头节点 dummy，其 next 指向原链表头 head。

- 这样无论头节点是否被删除，都可以统一处理。

2. 双指针遍历

- 使用 prev 指针指向当前节点的前一个节点，`current` 指针指向当前节点。

- 遍历链表：

- 如果 current->val == val，则删除当前节点：`prev->next = current->next`。

- 否则，`prev` 向后移动到 current。

- current 每次都向后移动。

3. 返回结果

- 最后返回 dummy->next，即新的链表头。

### 代码实现

class Solution {
public:
	ListNode* removeElements(ListNode* head, int val) {
		//返回出去的虚拟头节点
		ListNode* dummy = new ListNode(0,head);
		ListNode* current = dummy->next; // 当前指针指向虚拟头节点
		ListNode* prev = dummy; // 前一个指针指向虚拟头节点
		while (current != nullptr) {
			if (current->val == val) {
				prev->next = current->next; // 如果当前节点的值等于val，则删除当前节点
			}
			else {
				prev = current; // 如果当前节点的值不等于val，则前一个指针移动到当前节点
			}
			current = current->next; // 当前指针移动到下一个节点
		}

		return dummy->next; // 返回虚拟头节点的下一个节点作为新的头节点

	}
};