【力扣】移除链表元素203

2023-12-13 04:31:28

1.前言

这里开始介绍从网上一些刷题网站上的题目,在这里做一些分享,和学习记录。
先来介绍一些力扣的OJ题目。
这里的OJ就是我们不需要写主函数,力扣会提供一个接口,在力扣中会调用我们所写的代码和它后台的匹配,从而判断我们写的代码正确性。

在力扣的题目中一般会给一些示例,就像这样:
在这里插入图片描述
当我们写完代码时可以点击运行,这时下面会出现一些测试用例,就像下面这样:
在这里插入图片描述
但是并不是给了运行成功就一定能成功,必须点击上面的提交,通过了才是真正的正确,就像下面这样:
在这里插入图片描述

2. 题目描述

在这里插入图片描述

3. 题目分析

这里题目明确指出需要返回的是新的链表,所以要返回一个新链表的头节点。
当我们没有任何思路时,可以先看看它给的示例,先进行一下分析。
在这里插入图片描述
要找到不是val值的节点,那么首先肯定要先遍历原来的链表,把不是的插入到新的链表中。

那首先就得先定义一个新的链表的头指针struct ListNode* newhead=NULL;为了方便实现插入,使用尾插,再定义一个新链表的尾指针方便插入struct ListNode* tail=NULL;接下来就需要原链表中找出不是val值的节点,然后尾插就行。

怎么找出不是val值的节点?
为了不使原链表中的头节点丢失,用定义一个cur指针代替,struct ListNode* cur=head;
用一个while循环,当cur为空时就结束,也就是cur已经把原链表遍历完了。

这里需要先考虑一下如果原链表为空,那就直接返回NULL就行。

在循环中怎么写找到val的代码?
那就先让cur往后走,当走到cur->val=val结束,所以这里插入的条件就是if(cur->val!=val),然后开始实现尾插。

3.1 不带哨兵位

这里还需要先判断一下新的链表是不是为空,如果为空,那就直接将cur=newhead,并且更新一下tail=cur;如果不为空,那就直接实现尾插。

        if(cur->val!=val)
        {
            if(newhead==NULL)
            {
                newhead=cur;
                tail=cur;
            }
            else
            {
                 tail->next=cur;
                 tail=tail->next;
            }

然后让cur继续往后遍历。
当找到原链表中节点值为val的节点是时,就删除:

struct ListNode* tmp=cur;
         cur=cur->next;
         free(tmp);

这里加一个尾指针的判断

if(tail)
    {
        tail->next=NULL;
    }

最后直接返回新节点的头指针。
在这里插入图片描述

3.2 带哨兵位

使用带哨兵位的新链表, newhead=tail=(struct ListNode*)malloc(sizeof(struct ListNode));就不需要判断新链表是否为空。
其它地方都与不带哨兵位一样,不过最后得把申请的哨兵位释放掉,返回的是哨兵位的后一个节点。

     struct ListNode* tmp=newhead;
     newhead=newhead->next;
     free(tmp);

    return newhead;  

在这里插入图片描述

4. 附代码

4.1 不带哨兵位


struct ListNode* removeElements(struct ListNode* head, int val) 
{
    struct ListNode* newhead=NULL;
    struct ListNode* tail=NULL;
    struct ListNode* cur=head;
    while(cur)
    {
        if(cur->val!=val)
        {
            if(newhead==NULL)
            {
                newhead=cur;
                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;    
}

4.2 带哨兵位


struct ListNode* removeElements(struct ListNode* head, int val) {
   
    struct ListNode* newhead=NULL;
    struct ListNode* tail=NULL;
    struct ListNode* cur=head;

    newhead=tail=(struct ListNode*)malloc(sizeof(struct ListNode));

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

    return newhead;   
}

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