Leetcode: 203. 移除链表元素

2023-12-19 22:20:02

题目

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

难度:简单

题目链接:203. 移除链表元素

示例 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
输出:[]

方法一:?

题目解析:

遍历链表,删除指定元素(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; //返回新的头节点
}

删除元素的主要思想

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

?于是这里采用双指针

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

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

第一步

第二步

?

?删除的结点是第一个结点时:

即此时的 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)? ?--- (只有 一个结点 的情况 而且 是要删除的结点)

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

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

之后再去重复上述第二步,直到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;
}

图解

文章来源:https://blog.csdn.net/qq_72505850/article/details/134190204
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。