C++算法练习-day6——203.移除链表元素

题目：. - 力扣（LeetCode）

题目思路分析

题目要求从一个单链表中移除所有值等于给定值的节点。这个问题是链表操作中的常见问题，通常可以通过迭代的方式解决。移除节点时，需要考虑边界情况，比如移除头节点或者连续节点的情况。为了避免处理这些特殊情况带来的复杂性，通常会引入一个虚拟头节点（dummy head），这样可以使代码更加简洁和统一。

代码(参考代码随想录）：

/**  * 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) {  // 创建一个虚拟头节点，其next指向原链表的头节点  ListNode* dummyHead = new ListNode(0);  dummyHead->next = head;  // 使用cur指针遍历链表  ListNode* cur = dummyHead;  // 当cur的next不为空时，继续遍历  while (cur->next != NULL) {  // 如果当前节点的下一个节点的值等于给定值  if(cur->next->val == val) {  // 记录要删除的节点  ListNode* tmp = cur->next;  // 将当前节点的next指向要删除节点的下一个节点，从而删除该节点  cur->next = cur->next->next;  // 释放已删除节点的内存  delete tmp;  } else {  // 如果下一个节点的值不等于给定值，则继续遍历  cur = cur->next;  }  }  // 更新头节点为虚拟头节点的下一个节点  head = dummyHead->next;  // 释放虚拟头节点的内存  delete dummyHead;  // 返回新的头节点  return head;  }  
};

知识点摘要

1. 链表的基本操作：链表的创建、遍历、节点删除等。
2. 虚拟头节点：在处理链表问题时，为了简化边界条件的处理，通常会引入一个虚拟头节点。
3. 内存管理：在C++中，使用new关键字分配的内存需要在适当的时候使用delete关键字释放，以避免内存泄漏。

本文介绍了一种通过引入虚拟头节点来移除单链表中所有值等于给定值的节点的方法。这种方法通过统一处理头节点和其他节点的删除操作，简化了代码逻辑。在遍历链表的过程中，通过检查当前节点的下一个节点的值是否等于给定值来决定是否删除该节点。当删除节点时，需要确保正确更新指针并释放已删除节点的内存。最后，更新头节点为虚拟头节点的下一个节点，并释放虚拟头节点的内存。这种方法不仅解决了问题，还展示了链表操作的一些基本技巧和注意事项。