Leetcode: 203. 移除链表元素

比眉伴天荒 2024-02-20 12:40 39阅读 0赞

**题目**

> 给你一个链表的头节点 `head` 和一个整数 `val` ，请你删除链表中所有满足 `Node.val == val` 的节点，并返回 **新的头节点** 。
> 
> 难度：简单
> 
> 题目链接：[203. 移除链表元素][203.]

**示例 1：**

![924dc01f98ef31193d8faad3665c17bd.jpeg][]

输入：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
    输出：[]

**方法一：**

**题目解析：**

遍历链表，删除指定元素(val)

**代码展示**

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    
    
    struct ListNode* removeElements(struct ListNode* head, int val){
        struct ListNode* pre = NULL,*cur = head;
        while(cur)
        {
            if(cur->val == val)
            {
                struct ListNode* next = cur->next;
                free(cur);
                if(pre == NULL) //删除第一个节点时，free之后，head就变成了也指针
                {
                    //为了避免head变成野指针
                    head = next;
                }
                else
                {
                    pre->next = next;
                }
                cur = next;//继续去找元素
            }
            else
            {
                pre = cur;
                cur = cur->next;
            }
        }
        return head; //返回新的头节点
    }

删除元素的**主要思想**

![d7faef369e774ab9a7ab64ad7b656752.png][]

**这样的话就要考虑如何找被删除元素的前一个结点，和被删除元素的下一个结点。**

于是这里采用**双指针**

**pre 指针 记录前一个结点，cur 记录指向的当前结点**

前提是：删去的不是第一个结点的情况下

**第一步**

![3adf58aa2aa04e83af97aef631d82b5a.png][]

**第二步**

![f94350a64a7a4d2b8cd0703d98d260db.png][]

删除的结点是第一个结点时：

即此时的 pre 是NULL ,cur指向的是head(第一个结点)，删去结点（free(cur)）。

这里free(cur) 会把第一个结点的内存空间释放返回给操作系统，pre->next = next;会出现问题

加上

if(pre == NULL) //删除第一个节点时，free之后，head就变成了也指针
                {
                    //为了避免head变成野指针
                    head = next;
                }
                else
                {
                    pre->next = next;
                }
                cur = next;//继续去找元素

if(pre == NULL) --- (**只有 一个结点 的情况 而且 是要删除的结点**)

![9efd881c52d141718325c8bfe7d2684a.png][]

这种情况直接让 head 指向 next(代表cur->next,这里也就是NULL)

因为 要删除的元素可能不仅仅是一个，也有可能是多个。所以**每次删完一个元素的时候，注意pre指针的指向和cur指针的指向**

![68e43b3ce3de40b995d4a69f7c76bb1a.png][]

之后再去重复上述第二步，直到cur遍历完链表。

**方法二**

**主要思想：**

先让cur指向第一个结点，遍历结点，把不等于val的值给放到新的链表里。然后返回新的链表头指针即可。

**代码**

struct ListNode* removeElements(struct ListNode* head, int val){
        struct ListNode* newhead = NULL,*tail = NULL;
        struct ListNode* cur = head;
        while(cur)
        {
            if(cur->val != val )
            {
                if(tail == NULL)
                {
                    newhead = tail = cur;
                }
                else
                {
                    tail->next = cur;
                    tail = tail->next;
                }
                cur = cur->next;
            }
            else
            {
                struct ListNode* tmp = cur;
                cur = cur->next;
                free(tmp);
            }
        }
        if(tail)
            tail->next = NULL;
        return newhead;
    }

**图解**

![3aceb9a6fe7f4425a84722ddce0232bb.png][]

![3c65e15cc2f6469ca6bb0aa564da75e9.png][]

[203.]: https://leetcode.cn/problems/remove-linked-list-elements/description/
[924dc01f98ef31193d8faad3665c17bd.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/939377acd29a495db138a35319d50f04.png
[d7faef369e774ab9a7ab64ad7b656752.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/f9090e04f9274d10aff5ad9fa6326900.png
[3adf58aa2aa04e83af97aef631d82b5a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/e98ed1fbc38b4e3bb78ef759b32c0c21.png
[f94350a64a7a4d2b8cd0703d98d260db.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/2519583d84904ab4a396d57929addb8a.png
[9efd881c52d141718325c8bfe7d2684a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/094f7dfc265a4daf86dea6717d25ac07.png
[68e43b3ce3de40b995d4a69f7c76bb1a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/0a9eb3b75e844c019621c37d581fed02.png
[3aceb9a6fe7f4425a84722ddce0232bb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/28cf95cba94c4d5d9e836079bd38da19.png
[3c65e15cc2f6469ca6bb0aa564da75e9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/df49ef9eb1354a509a11b470e6f60785.png