【力扣】移除链表元素203
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;
}
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!