C++链表相关内容温习回顾——移除链表元素

   本文主要对之前学过的C++链表相关内容进行温习回顾，并以 移除链表元素 为例，进行应用。

   关于链表的基础理论可见：链表理论基础

   应用示例：LeetCode 203 移除链表元素

   https://leetcode.cn/problems/remove-linked-list-elements/

   0、例题描述如下：

   1、带详细注释的可在本地IDE运行的C++链表实现如下：

#include<iostream>
#include<vector>using namespace std;// 定义链表的节点结构
struct ListNode
{int val;  // 节点存储的值ListNode* next;  // 指向下一个节点的指针ListNode() :val(0), next(nullptr) {}  // 默认构造函数ListNode(int x) :val(x), next(nullptr) {}  // 构造函数初始化值ListNode(int x, ListNode* ptr) :val(x), next(ptr) {}  // 构造函数初始化值和指针
};// 定义解决问题的类
class Solution
{
public:// 移除链表中所有值为val的节点ListNode* removeElements(ListNode* head, int val){  ListNode* vhead = new ListNode(0);  // 创建虚拟头节点以简化边界处理vhead->next = head;  // 将虚拟头节点指向实际的头节点ListNode* cur = vhead;  // 使用cur遍历链表while (cur->next != nullptr)  // 遍历链表直到尾部{if (cur->next->val == val)  // 如果当前节点的下一个节点的值等于val{ListNode* temp = cur->next;  // 临时保存需要删除的节点cur->next = cur->next->next;  // 将当前节点的指针指向下下个节点delete temp;  // 删除节点释放内存}else{cur = cur->next;  // 移动到下一个节点}}head = vhead->next;  // 更新头节点delete vhead;  // 删除虚拟头节点return head;  // 返回新的头节点}
};int main()
{// 创建测试链表 [1,2,6,3,4,5,6]ListNode* head = new ListNode(1);head->next = new ListNode(2);head->next->next = new ListNode(6);head->next->next->next = new ListNode(3);head->next->next->next->next = new ListNode(4);head->next->next->next->next->next = new ListNode(5);head->next->next->next->next->next->next = new ListNode(6);Solution solution;int val = 6;head = solution.removeElements(head, val);  // 调用removeElements函数移除值为6的节点// 打印新的链表ListNode* cur = head;while (cur != nullptr)  // 遍历链表打印每个节点的值{cout << cur->val << " ";cur = cur->next;}cout << endl;// 释放链表内存cur = head;ListNode* next;while (cur != nullptr){next = cur->next;  // 保存下一个节点delete cur;  // 删除当前节点cur = next;  // 移动到下一个节点}
}

   运行结果如下：

–

   2、程序的详细介绍

   这个程序实现了一个特定的链表操作，即删除链表中所有值等于给定整数 val 的节点。程序分为几个主要部分：

   1. ListNode 结构体：定义链表的节点，每个节点包含一个整数值 val 和一个指向下一个节点的指针 next。

   2. Solution 类：

   - removeElements 方法：这是类的主要方法，用于移除链表中所有值为 val 的节点。方法通过添加一个虚拟头节点来简化边界条件的处理，然后遍历链表，逐个检查每个节点的值。

   3. main 函数：

   - 创建并初始化链表。

   - 调用 removeElements 方法处理链表。

   - 打印处理后的链表结果。

   - 释放链表中所有节点的内存，以防止内存泄漏。

   4. 函数语句的详情介绍见上面代码的注释：

   这个程序特别适用于学习和理解链表的操作，特别是如何处理删除链表节点时的边界条件。通过使用虚拟头节点，代码更加简洁，逻辑更清晰。

   3、LeetCode 核心代码模式源码：

/*** 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){  ListNode* vhead = new ListNode(0);vhead->next = head;ListNode* cur = vhead;while (cur->next != nullptr){if (cur->next->val == val){ListNode* temp = cur->next;cur->next = cur->next->next;delete temp;}else{cur = cur->next;}}head = vhead->next;delete vhead;return head;}
};

   4、一种可能的ACM模式源码：

   由于未知具体的输入给定形式，本例子中以如下所示的输入格式为例

[1,2,6,3,4,5,6] 6

   示例程序如下：

#include<iostream>
#include<vector>using namespace std;struct ListNode {int val;ListNode* next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode* ptr) : val(x), next(ptr) {}
};class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* vhead = new ListNode(0);  // 创建虚拟头节点以简化边界处理vhead->next = head;ListNode* cur = vhead;while (cur->next != nullptr) {if (cur->next->val == val) {ListNode* temp = cur->next;cur->next = cur->next->next;delete temp;} else {cur = cur->next;}}head = vhead->next;delete vhead;return head;}
};int main() {vector<int> nums;int num, val;char ch;// 读取链表数值，以及需要移除的数值while (cin >> ch && ch != ']') { // 读取直到遇到 ']'if (cin >> num) {nums.push_back(num);cin >> ch; // 读取逗号或者结束的 ']'}}cin >> val; // 读取需要移除的数值// 构建链表ListNode* head = nullptr, * tail = nullptr;for (int number : nums) {ListNode* newNode = new ListNode(number);if (!head) {head = tail = newNode;} else {tail->next = newNode;tail = newNode;}}Solution solution;head = solution.removeElements(head, val);// 输出新链表ListNode* cur = head;if (cur) {cout << cur->val;cur = cur->next;}while (cur) {cout << "," << cur->val;cur = cur->next;}cout << endl;// 释放链表内存cur = head;ListNode* next;while (cur) {next = cur->next;delete cur;cur = next;}
}

   参考输入的运行结果如下：

1,2,3,4,5