[数据结构与算法] LeetCode--203.移除链表元素（C++）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> LeetCode--203.移除链表元素（C++） -> 正文阅读

[数据结构与算法]LeetCode--203.移除链表元素（C++）

力扣链接

题意：删除链表中等于给定值 val 的所有节点。

示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：
输入：head = [], val = 1
输出：[]

示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]

Clion 中的乱码问题正确解决方案（来自官方技术支持）

解法一：直接使用之前的链表进行移除结点操作

//
// Created by lwj on 2022-04-13.
//
#include <iostream>
#include <vector>

using namespace std;

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    //ListNode(int x) : val(x), next(NULL) {}  // 有参数的节点的构造函数
    ListNode() : val(), next() {} //无参数的构造函数
};

ListNode* creatList(int n) {
    ListNode* head = new ListNode(); // 头结点 不存储数据
    head->next = NULL;
    ListNode* pre = head; // 指向下一个节点的过渡值

    cout << "请依次输入" << n << "个链表的值";
    for (int i = 0; i < n; i++) {
        ListNode* temp = new ListNode;
        cin >> temp->val;

        pre ->next = temp;
        pre = temp;
        temp->next = nullptr;
    }
    return head;
}
void display(ListNode* head){
    ListNode* temp = head->next;
    int e;
    cout << "该链表的遍历顺序为：";
    while (temp != nullptr) {
        e = temp->val;
        cout << e << " ";
        temp = temp->next;
    }
    cout << "\n";
}
class Solution {
public:
   ListNode* removeElements(ListNode* head, int val) {
       // 删除头结点
       while (head != NULL && head->val == val) { // head是个指针名字，指向一块地址，当头指针不为空并且第一个节点的val值是要删除的值时，就将头指针指向下一个节点
           ListNode* temp = head; // 将原始的头结点保存到temp中，这么做是为了释放内存
           head = head->next;
           delete temp;
       }
       // 删除非头结点
       ListNode* cur = head; // 将原始的头结点保存到cur中
       while (cur != NULL && cur->next!=NULL){ // 当cur结点不为空，并且cur结点的下一个节点也不为空时
            if (cur->next->val == val) { //如果cur结点的下一个节点的val是要找的值时
                ListNode* temp = cur->next; //保存下这个即将删除的结点，目的是为了释放它占用的内存
                cur->next = cur->next->next; //就让cur结点的next指向下下个结点
                delete temp;
            } else { // 如果cur的下一个结点的val值不是要删除的值，就让cur向后移动
                cur = cur->next;
            }
       }
       return head;//最后返回头结点
   }
};
int main() {
    Solution solution;
    int nums,val;
    cout << "请输入链表的长度";
    cin >> nums;
    ListNode* head = creatList(nums);
    display(head);
    cout << "请输入你要删除的值:";
    cin >> val;
    ListNode* test = solution.removeElements(head,val);
    display(test);
}

单链表的建立初始化，以及c++的结构体构造函数等问题参考下面链接：

C++：创建链表的过程详解

C++ - 结构体构造函数使用总结

解法二：设置一个虚拟头结点进行删除结点操作。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
        ListNode* cur = dummyHead;
        while (cur->next != NULL) {
            if(cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};