203_移除链表元素
【问题描述】
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例一：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例二：
输入：head = [], val = 1
输出：[]
示例三：
输入：head = [7,7,7,7], val = 7
输出：[]
提示：
- 列表中的节点数目在范围
[0, 104]内 1 <= Node.val <= 500 <= val <= 50
【算法设计思想】
- 首先是应对重复出现的情况，例如1、1、1、1、这样的链表，我们可以使用一个while循环来逐个删除。
- 然后是检查head，即当前链表是否为空，如果是空，那么我们直接返回head就好了。
- 最后是一般情况，使用while循环来处理一般的情况，在这里需要注意prev->next->val的值不是val时才移动指针，否则会出现跳过重复元素的情况。
【算法描述】
C++:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// 移除所有位于链表头部且值为val的节点
while (head != nullptr && head->val == val) {
ListNode* toDelete = head; // 保存当前头节点
head = head->next; // 更新头节点为下一个节点
delete toDelete; // 释放被删除节点的内存
}
// 如果链表为空，直接返回
if (head == nullptr)
return head;
// 初始化 prev 指针，从头节点开始
ListNode* prev = head;
// 遍历链表，移除值为val的节点
while (prev->next != nullptr) {
if (prev->next->val == val) {
ListNode* temp = prev->next; // 保存需要删除的节点
prev->next = temp->next; // 跳过需要删除的节点
delete temp; // 释放被删除节点的内存
} else {
prev = prev->next; // 只有当 prev->next 的值不是 val 时才移动 prev 指针
}
}
return head; // 返回处理后的链表头节点
}
};
Java：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
// 移除所有位于链表头部且值为val的节点
while (head != null && head.val == val) {
ListNode toDelete = head; // 保存当前头节点
head = head.next; // 更新头节点为下一个节点
toDelete = null; // 释放被删除节点的引用，让垃圾回收器回收
}
// 如果链表为空，直接返回
if (head == null) {
return head;
}
// 初始化 prev 指针，从头节点开始
ListNode prev = head;
// 遍历链表，移除值为val的节点
while (prev.next != null) {
if (prev.next.val == val) {
ListNode temp = prev.next; // 保存需要删除的节点
prev.next = temp.next; // 更新 prev.next 指向下一个节点
temp = null; // 释放被删除节点的引用，让垃圾回收器回收
} else {
prev = prev.next; // 只有当 prev.next 的值不是 val 时才移动 prev 指针
}
}
return head; // 返回处理后的链表头节点
}
}
Python：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
# 移除所有位于链表头部且值为val的节点
while head is not None and head.val == val:
toDelete = head # 保存当前头节点
head = head.next # 更新头节点为下一个节点
del toDelete # 释放被删除节点的内存
# 如果链表为空，直接返回
if head is None:
return head
# 初始化 prev 指针，从头节点开始
prev = head
# 遍历链表，移除值为val的节点
while prev.next is not None:
if prev.next.val == val:
temp = prev.next # 保存需要删除的节点
prev.next = temp.next # 更新 prev.next 指向下一个节点
del temp # 释放被删除节点的内存
else:
prev = prev.next # 只有当 prev.next 的值不是 val 时才移动 prev 指针
return head # 返回处理后的链表头节点
C：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val) {
// 移除所有位于链表头部且值为val的节点
while (head != NULL && head->val == val) {
struct ListNode* temp = head; // 保存当前头节点
head = head->next; // 更新头节点为下一个节点
free(temp); // 释放被删除节点的内存
}
// 如果链表为空，直接返回
if (head == NULL) {
return head;
}
// 初始化 prev 指针，从头节点开始
struct ListNode* prev = head;
// 遍历链表，移除值为val的节点
while (prev->next != NULL) {
if (prev->next->val == val) {
struct ListNode* temp = prev->next; // 保存需要删除的节点
prev->next = temp->next; // 更新 prev.next 指向下一个节点
free(temp); // 释放被删除节点的内存
} else {
prev = prev->next; // 只有当 prev.next 的值不是 val 时才移动 prev 指针
}
}
return head; // 返回处理后的链表头节点
}