203_移除链表元素

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 <= 50
• 0 <= val <= 50

【算法设计思想】

1. 首先是应对重复出现的情况，例如1、1、1、1、这样的链表，我们可以使用一个while循环来逐个删除。
2. 然后是检查head，即当前链表是否为空，如果是空，那么我们直接返回head就好了。
3. 最后是一般情况，使用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 = nextclass 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; // 返回处理后的链表头节点
}