【链表】LeetCode:203.移除链表元素

🎁个人主页：我们的五年

🔍系列专栏：每日一练

🌷追光的人，终会万丈光芒

 前言：

该题是数据结构，单链表的一道基本题，刚刚准备学习数据结构，或者正在学习数据结构的可以学习一下。

题目链接：203. 移除链表元素 – 力扣（LeetCode）

最后喜欢的铁子们可以三连，谢谢大家的支持！祝大家天天开心！

目录

目录

🏝1.问题描述：

​编辑

1.题目描述：

2.示范用例：

🏝2.实现代码：

🏝3.代码分析：

🏜步骤一：

🏜步骤二：

🏜步骤三：

❗️注意：

🚗总结：

🏝1.问题描述：

1.题目描述：

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

2.示范用例：

🏝2.实现代码：

LeetCode以函数的形式给出：

节点结构体：

struct ListNode{

        int val;

        struct ListNode* next;

};

传递也是传递的是指向头节点的指针

 typedef struct ListNode ListNode;    //重定义struct ListNode
struct ListNode* removeElements(struct ListNode* head, int val) {
    
    //对链表进行判空处理
    if(head==NULL)
        return head;
    
    //定义新节点的头和尾，一开始头节点等于尾节点
    //定义头节点，可以把后面不等于val的节点直接进行尾插，不要进行判空处理。
    ListNode *NewHead,*NewTail;
    NewHead=NewTail=(ListNode*)malloc(sizeof(ListNode));

    //pcur指针对原链表进行遍历
    ListNode *pcur=head;
    while(pcur)
    {
        //对满足题意的节点进行尾插，NewTail每次尾插要记得往后面移动
        if(pcur->val!=val)
        {
            NewTail->next=pcur;
            NewTail=NewTail->next;
        }
        //pcur每次都向后进行移动
        pcur=pcur->next;
    }
    
    //最后如果尾节点的next指针不为NULL，那么需要我们自己去置为NULL
    //不然又会和后面的节点进行关联
    if(NewTail->next)
        NewTail->next=NULL;

    //最后返回头结点的next指针
    NewHead=NewHead->next;
    return NewHead;
}

🏝3.代码分析：

🏜步骤一：

    if(head==NULL)
        return head;

先对节点进行判空处理，因为节点数目可能为0,如果head为NULL，那么直接返回head。

如果不进行判空处理，后面可能会对NULL进行解应用，出现错误。

🏜步骤二：

    ListNode *NewHead,*NewTail;
    NewHead=NewTail=(ListNode*)malloc(sizeof(ListNode));

然后创建一个头节点，一个尾节点。通过NewHead->next我们可以找到第一个节点，然后返回这一个节点。NewTail是每次尾插时要用到的，在尾插的过程中，我们把NewTail的next

指针置为指向新插入的节点的指针，然后让NewTail变为新插入的节点。

🔍这样先申请一个黑头节点，我们就不要对新的头节点进行判空处理了。

🏜步骤三：

    ListNode *pcur=head;
    while(pcur)
    {
        //对满足题意的节点进行尾插，NewTail每次尾插要记得往后面移动
        if(pcur->val!=val)
        {
            NewTail->next=pcur;
            NewTail=NewTail->next;
        }
        //pcur每次都向后进行移动
        pcur=pcur->next;
    }
    改循环就是对节点val的值进行判断，然后进行尾插的一个过程，如果符合题意的节点我们就尾插，把NewTail的next变为pcur，新的NewTail变为pcur。

pcur一直进行往后遍历。

❗️注意：

上面三个步骤完成以后，这题差不多就完成，但是把上面的代码直接提交，我们会发现没有通过！

这是因为我们没有对尾节点的next进行处理，如果我们不进行处理，那么如果尾节点的next不是NULL，这样还是会与后面的节点进行关联，所以测试用例才会多出一个6.

    if(NewTail->next)
        NewTail->next=NULL;

但是如果我们在尾节点加上这样一句话，我们就可以避免这种情况，不要多输出后面的节点。

    NewHead=NewHead->next;

最后我们返回NewHead的next指针，也就是满足题意的第一个节点就可以通过题目用例了。

因为开始我们动态申请了一块空间，我们也可以先保存第一个节点，释放以后，再进行return操作。

🚗总结：

谢该题时，我们如果只是对空间情况进行考虑是远远不够的，我们还需要对头部2进行分析，对尾部进行分析，这样我们能尽可能的满足题目要求，不会出现其他小的错误。

最后，我也会把也会我不会的题目，或者我觉得值得重点关注的问题在我的博客进行分享，希望大家可以多多支持！