小阳同学刷题日记-203. 移除链表元素

本文主要是介绍小阳同学刷题日记-203. 移除链表元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

思路：

两种思路：① 不创建虚拟节点的思路；② 创建虚拟节点的思路。

① 不创建虚拟节点的思路

首先处理头节点，如果头节点的值等于 val，则将头节点后移直到其值不等于 val。
然后遍历链表，删除所有值为 val 的节点。
需要维护一个指针 prev 指向当前节点的前一个节点，以便在删除节点时重新连接链表。
删除节点的方法是将 prev 节点的 next 指针指向当前节点的下一个节点，并释放当前节点的内存空间。
如果当前节点的值不等于 val，则将 prev 指针移动到当前节点，继续遍历下一个节点。
遍历结束后，返回头节点作为新的头节点

② 创建虚拟节点的思路

创建一个虚拟头节点 dummyHead，使其 next 指向原链表的头节点 head。
使用指针 cur 遍历链表，初始时指向虚拟头节点 dummyHead。
在遍历过程中，如果当前节点的下一个节点的值等于 val，则删除该节点。
删除节点的方法是将当前节点的 next 指针指向下下个节点，并释放被删除节点的内存空间。
如果当前节点的下一个节点的值不等于 val，则将 cur 指针移动到下一个节点。
遍历结束后，返回虚拟头节点 dummyHead 的下一个节点作为新的头节点。

代码：

① 不创建虚拟节点的代码

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {// 删除头节点while(head != NULL && head->val == val){ // 当头节点的值等于给定值时循环删除ListNode* temp = head; // 临时指针指向头节点head = head->next; // 移动头指针到下一个节点delete temp; // 释放被删除的头节点}// 删除非头节点ListNode* cur = head; // 使用cur指针遍历链表，初始指向头节点while(cur != NULL && cur->next != NULL){ // 循环直到cur指针指向链表尾节点的下一个节点或cur指针为空if(cur->next->val == val){ // 如果当前节点的下一个节点的值等于给定值ListNode* temp = cur->next; // 临时指针指向当前节点的下一个节点cur->next = cur->next->next; // 将当前节点的下一个节点指针指向下下个节点delete temp; // 释放被删除的节点}else{ // 如果当前节点的下一个节点的值不等于给定值cur = cur->next; // 移动当前节点指针到下一个节点}}return head; // 返回处理后的链表头节点指针}
};

② 创建虚拟节点的代码

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummyHead = new ListNode(0); // 创建虚拟头节点，值为0dummyHead->next = head; // 将虚拟头节点指向原链表的头节点ListNode* cur = dummyHead; // 使用cur指针遍历链表，初始指向虚拟头节点while(cur->next != NULL){ // 循环直到cur指针指向链表尾节点的下一个节点或cur指针为空if(cur->next->val == val){ // 如果当前节点的下一个节点的值等于给定值ListNode* temp = cur->next; // 临时指针指向当前节点的下一个节点cur->next = cur->next->next; // 将当前节点的下一个节点指针指向下下个节点delete temp; // 释放被删除的节点}else{ // 如果当前节点的下一个节点的值不等于给定值cur = cur->next; // 移动当前节点指针到下一个节点}            }return dummyHead->next; // 返回处理后的链表头节点指针，即虚拟头节点的下一个节点}
};

两种方法各有优缺点，我们来分析一下：