【LeetCode】移除链表元素（C语言）| 图解算法，超详细哦~

文章目录

- （1）题目描述
- （2）解题思路
- - 1）思路1：找到等于 val 的节点直接删除
  - 2）思路2：将不等于 val 的节点尾插到一个新链表中

《题目难度：简单》

（1）题目描述

给你一个链表的头节点 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

输出：[ ]

LeetCode链接：203. 移除链表元素

（2）解题思路

1）思路1：找到等于 val 的节点直接删除

定义一个指针 cur，用来遍历链表，找到等于 val 的节点

定义一个指针 prev，保存 cur 的上一个节点的位置

定义一个指针 next，保存 cur 的下一个节点的位置，用来迭代

首先判断 cur 指向节点的值是否等于 val：

如果等于，则要删除这个节点。我们需要将 prev->next 指向 next 指针，然后 free(cur)，再将 cur 往前移动到 next 指针的位置，这样就完成对这个节点的删除啦

如果不等于，只需要将 prev 指针和 cur 指针往前移动一位即可，继续遍历链表寻找等于 val 的节点
最后返回头节点指针 head 即可

需要考虑这一点

如果要删除的节点是头节点，所以在删除的时候需要额外判断一下是不是头结点。

代码如下

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* removeElements(struct ListNode* head, int val){
    //解题思路：遍历链表，找到满足Node.val == val的节点
    struct ListNode* cur = head;
    struct ListNode* prev = head;  //保存cur的上一个节点位置
    while(cur != NULL)  //遍历链表
    {
        if(cur->val == val)  //找到等于val的节点
        {
            struct ListNode* next = cur->next;  //保存cur的下一个节点位置
            if(head == cur)  //判断cur是否是头节点
            {
                head = next;
            }
            else
            {
                prev->next = next;  //将cur上一个节点和cur下一个节点相连
            }
            free(cur);  //删除等于val的节点
            cur = next;
        }
        else if(cur->val != val)
        {
            prev = cur;
            cur = prev->next; 
        }
    }
    return head;
}

2）思路2：将不等于 val 的节点尾插到一个新链表中

把链表中所有不等于 val 的节点尾插到一个新链表中，相当于删除了等于val的节点
定义一个指针 cur，用来遍历原链表，找到不等于 val 的节点
定义一个指针 newhead，指向新链表的头节点
定义一个指针 tail，保存新链表尾节点的位置

首先判断 cur 指向节点的值是否不等于 val：

如果不等于，则需要将其尾插到新链表中，首次尾插时，新链表为空，我们让 newhead 指向 cur，然后让 tail 指向 cur，更新新链表的尾节点，cur 往后移动一位，指向待遍历的下一个节点，最后将尾节点的 next 指针置空。

如果等于，则要删除这个节点。定义一个指针 next 保存 cur 的下一个节点的位置，然后 free(cur)，再将 cur 移动到 next 的位置，继续遍历原链表。
最后返回新链表的头节点指针 newhead 即可

代码如下

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* removeElements(struct ListNode* head, int val){
    //解题思路：把链表中所有不等于val的节点尾插到一个新链表中，相当于删除了等于val的节点
    struct ListNode* newhead = NULL;  //新链表初始为空
    struct ListNode* tail = newhead;  //记录新链表尾节点的位置
    struct ListNode* cur = head;
    while(cur != NULL)
    {
        if(cur->val != val)  //把链表中所有不等于val的节点尾插到一个新链表中
        {
            if(newhead == NULL)  //新链表为空时
            {
                newhead = cur;
            }
            else  //新链表不为空时
            {
                tail->next = cur;
            }
            tail = cur;  //更新尾节点
            cur = cur->next;  //cur指向原链表中的下一个节点
            tail->next = NULL;  //将尾节点置空
        }
        else if(cur->val == val)
        {
            struct ListNode* next = cur->next;  //保存cur的下一个节点位置
            free(cur);  //删除等于val的节点
            cur = next;
        }
    }
    return newhead;
}