力扣203 - 移除链表元素【LeetCode转VS调试技巧教学】

一、题目描述

原题传送门🚪

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == 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
输出：[]

提示：

• 列表中的节点数目在范围 [0, 104] 内
• 1 <= Node.val <= 50
• 0 <= val <= 50

二、思路分析

好，看完题目的描述，我们来分析一下如何去求解这道题目

• 对于本题，题目描述很清晰，给你一个链表的头结点和待删除的元素，但是这里大家要注意，这里给的头结点并不是指的带头结点的链表，只是对于这个链表而言的头部结点，是为了让你可以找到这个链表的所有结点。这里一开始就指出这点的原因是在本题中我要讲解的两种方法就是一个带头，一个不带头，为了避免大家混淆，所以事先讲清楚
• 然后来分析一下求解的思路，最简单直观的一种思路就是通过遍历去寻找待删结点，然后一一删除，但是这种做法在后期修改的过程中很是麻烦，有些测试案例需要你去不断测试修改，因此这种方法我不做讲解。
• 说一下我要讲解的方法，也就是重新定义一个链表，然后也是一样去一一遍历原先链表中的结点，若是发现不等于val的结点，则将其使用尾插放入新的链表。若是发现了待删结点，就将其删除，然后继续向下做遍历，直到整个链表遍历完成为止

三、代码详解

然后我们通过这段代码来给大家分析一下

way1【不带头结点】

• 首先应该要有一个指针指向原先的头结点，因为不能去移动原本的头结点，会将整个链表的结构损坏；接着就是定义这个新的链表头，用于返回，定义tail指针用于做结点的尾插操作，一开始要将他们置为空

struct ListNode* cur = head;
struct ListNode* tail, *newhead;
tail = newhead = NULL;
1
2
3

• 接着，就要开始执行内部循环遍历的逻辑，当这个cur指针不为空时，也就是还没有遍历到链表结尾，一直进行一个遍历
• 内部的判断逻辑分为两部分，一部分是【结点不为待删结点，拿过来尾插】，还有另一部分则是【结点为待删结点，实行删除结点操作】，我们通过图解来看一下

• 可以看到，第一个结点的值为1，不为待删结点元素5，因此将其进行一个尾插，但是一开始新链表为空，这个逻辑我们在尾插的时候有讲到过，若是只有一个结点的时候，那待插入的结点就是首部结点，于是直接进行一个赋值即可

if(tail == NULL){       //第一次拿过来
   newhead = tail = cur;
1
2

• 然后cur继续往后进行一个遍历，结点值为2 ≠ 6，因此将其插入到新链表中，此时需要实现的逻辑是一个尾插的逻辑，这个不复杂，我们看一下代码

• 只需要让tail->next = cur，进行一个尾部的链接，然后让这个tail向下走即可，当然cur指针也要继续向后走

tail->next = cur;
tail = tail->next;
```>![在这里插入图片描述](https://img-blog.csdnimg.cn/93c533f3c82140938286a0691b461380.jpeg#pic_center)
 - 接着我们可以看到此时的cur所指向的结点值为6，是我们需要的待删结点，此时就需要执行删除的逻辑，将其从链表中删除即可，然后的话既然它不是我们需要的元素，就不需要将其链接到新链表中，直接进行以下代码的操作即可
- 有一点，不要忘了保存待删结点的下一个结点，否则free之后就找不到了
```c
struct ListNode* nextNode = cur->next;         //首先保存下一结点
free(cur);
cur = nextNode;
1
2
3
4
5
6
7
8
9

• 然后我们直接快进到这里💽

• 此时3、4、5结点均被链接上，cur = cur->next来到了最后一个结点，而且当前结点也是待删结点，因此将其free，接着cur继续后移便跳出了循环，此时我们return newhead

• 当我们提交之后可以看到，后台报出了【执行错误】，首先你要做的是去分析为什么会报出这个错误，报出这个错误是哪方面出问题了，而不是去盯着代码看来看去👀。这个时候你只会感觉到越加心烦意乱，那有同学问，我看这个保存看不出来怎么办呢？这时候就有一个很好的办法------》【DeBug调试】

DeBug调试教学

此处为大家以视频的形式展现，温馨提示：【如果太模糊请左右拖动一下】

way2【带头结点】

• 好，看完了不带头结点的情况，接下来我们看一种带头结点的，这种方法需要去手动开辟一个虚拟头结点，但是对于首次的尾部结点插入无需考虑【tail】的情况
• 也就是最前面的这段逻辑需要进行一个修改，【guard】就是我们所说的哨兵位，首先第一步就是要将哨兵以及进行尾插的【tail】动态开辟出来

struct ListNode* cur = head;
struct ListNode* tail, *guard;
tail = guard = (struct ListNode*)malloc(sizeof(struct ListNode));
1
2
3

• 因此在程序的最后，无需判断tail是否为空的情况，也就不会存在我们视频中所讲的对空指针的操作
• 因为无需去判断是第一次尾插还是后面的尾插，因此当cur遍历到的结点不为待删结点时的内部逻辑就可以进行一个简化了，直接做一个链接然后让【tail】和【cur】后移即可

if(cur->val != val){
  tail->next = cur;
  tail = tail->next;
  cur = cur->next;
}
1
2
3
4
5

• 具体的插入操作入下图所示，原本有了一个头结点，因此直接进行尾插即可

四、整体代码展示【需要自取】

给出两种方法的代码

方法一：不带哨兵位【无头结点】

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val){
    if(head == NULL){
        return head;
    }
    struct ListNode* cur = head;
    struct ListNode* tail, *newhead;
    tail = newhead = NULL;

    while(cur)
    {
        //1.结点不为待删结点，拿过来尾插
        if(cur->val != val){
            if(tail == NULL){       //第一次拿过来
                newhead = tail = cur;
            }else{      //后续的尾插
                tail->next = cur;
                tail = tail->next;
            }
            cur = cur->next;
        }else{      //2.结点为待删结点，实行删除结点操作
            struct ListNode* nextNode = cur->next;         //首先保存下一结点
            free(cur);
            cur = nextNode;
        }
    }
    if(tail)
        tail->next = NULL;
    return newhead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

方法二：带哨兵位【有头结点】

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val){
    if(head == NULL){
        return head;
    }
    struct ListNode* cur = head;
    struct ListNode* tail, *guard;
    tail = guard = (struct ListNode*)malloc(sizeof(struct ListNode));

    while(cur)
    {
        //1.结点不为待删结点，拿过来尾插
        if(cur->val != val){
            tail->next = cur;
            tail = tail->next;
            cur = cur->next;
        }else{      //2.结点为待删结点，实行删除结点操作
            struct ListNode* nextNode = cur->next;         //首先保存下一结点
            free(cur);
            cur = nextNode;
        }
    }
    //tail不可能为空，一开始已经开出空间指向第一个结点
    tail->next = NULL;

    struct ListNode*next = guard->next;
    free(guard);
    return next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

五、总结与提炼

• 好，我们来总结一下本文所学习的知识，在本文中我是讲解了一道力扣的题解，为力扣203的【移除链表元素】，在文中我给出了两种方法，一种是带头结点，一种是不带头结点。对于不带头结点的，我在第一次提交之后进行了一个视频讲解，相信看了之后你应该能明白要如何将LeetCode上的代码放到VS上面去调试运行，然后一步步地跟着程序的逻辑进行调试。从中大家应该也明白了在C/C++中对于指针的操作是需要多么地谨慎，可能你一个不小心就会使一个指针变为野指针，或者去操作一个空指针
• 希望在看了本文之后，你不仅可以对力扣上的报错有了一个分析的能力，而且也能学会如何使用VS去调试力扣上的代码

以上就是本文所要描述的所有内容，感谢您对本文的观看，如有疑问请于评论区留言或者私信我都可以🍀