给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。(题目来源)
要移除链表中值为val的结点,我们肯定是要将链表遍历一遍,关键是我们在遍历的过程中应该如何操作。我们考虑问题的时候,可以先考虑比较常见的情况,再考虑特殊情况。
一、考虑常见情况
要移除某一结点,也就是让该结点的前一个结点指向待移除结点的后一个结点,然后将待移除结点释放即可。我们可以定义3个指针变量:prev,cur,next 。
prev:记录待排查结点的前一个结点位置(previous)。
cur:记录当前正在排查的结点位置(current)。
next:记录待排查结点的后一个结点(next)。
当cur指针指向的结点并非待移除的结点时,3个结点依次向后移动。
当cur指针指向待移除的结点时,我们首先让prev指针指向的结点指向next,然后将cur指针指向的结点释放掉,并将next指针赋值给cur指针,next指针再后移。
如此进行下去,直到链表遍历完毕,那么值为val的结点也就删除了。
二、考虑特殊情况
常见情况的分析往往只能解决问题的一般情况,并不能解决问题的极端情况。要真正解决问题,我们需要考虑到问题的极端情况。例如,当待移除的结点是第一个结点或是最后一个结点的情况,当链表为空的情况。
1.当链表的第一个结点为待移除的结点时
这时我们需要先将头指针指向next,然后释放cur指向的结点,并将next指针赋值给cur指针,next指针再后移。
2.当链表的最后一个结点为待移除的结点时
当排查到最后一个结点时,cur指向最后一个结点,next指针指向该结点指向的位置,即NULL。
我们用上面常规情况的方法对其进行分析,发现常规情况的思路适用于这种特殊情况。并且发现遍历的终止条件,就是当cur为NULL的时候遍历停止。
3.当传入链表为空时
我们可以发现,若传入的链表为空链表(NULL),cur指针的值一开始就为空,而我们遍历的终止条件就是当cur为NULL时停止遍历,所以当传入链表为空时,直接执行到函数末尾,即返回头指针(NULL)。
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* prev = NULL;//记录待排查结点的前一个结点位置
struct ListNode* cur = head;//记录当前正在排查的结点位置
while (cur != NULL)//当cur为空时,循环停止
{
if (cur->val == val)//当前排查的结点是待移除的结点
{
struct ListNode* next = cur->next;//记录待排查结点的后一个结点位置
if (cur == head)//待移除的结点是链表的第一个结点
{
head = next;//头指针指向next
free(cur);//释放第一个结点
cur = next;//将next指针赋值给cur指针
}
else//待移除的结点不是链表的第一个结点
{
prev->next = next;//prev指针指向的结点指向next
free(cur);//将cur指针指向的结点释放掉
cur = next;//将next指针赋值给cur指针
}
}
else//当前排查的结点不是待移除的结点
{
prev = cur;//指针后移
cur = cur->next;//指针后移
}
}
return head;//返回新的头指针
}
我们可能觉得思路一的代码比较复杂,当我们要移除某一个结点时,还需要判断该结点是否为第一个结点,那么有没有什么办法可以不用进行这一步操作呢?
回答是肯定的。办法就是在传入的链表前面强行加上一个头结点,并让链表原来的头指针指向该头结点,这样我们就不用判断待移除的结点是否为第一个结点了(因为现在第一个结点是头结点)。
在加了头结点后,我们就只需要根据常见情况的逻辑进行代码的编写即可。但是有一点不能忘记,就是在遍历完链表后要将头结点指向的位置(即第一个结点的位置)赋值给头指针,并将头结点释放掉,最后才能返回头指针。
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));//申请一个头结点,返回其地址
guard->next = head;//让头结点指向链表的第一个结点
struct ListNode* cur = guard->next;//cur指针指向原链表第一个结点
struct ListNode* prev = guard;//prev指针指向头结点
while (cur != NULL)//当cur为空时,循环停止
{
if (cur->val == val)//当前排查的结点是待移除的结点
{
struct ListNode* next = cur->next;//记录待排查结点的后一个结点位置
prev->next = next;//prev指针指向的结点指向next
free(cur);//将cur指针指向的结点释放掉
cur = next;//将next指针赋值给cur指针
}
else//当前排查的结点不是待移除的结点
{
prev = cur;//指针后移
cur = cur->next;//指针后移
}
}
head = guard->next;//将头结点指向的位置赋值给头指针,使头指针指向链表第一个结点
free(guard);//释放头结点
guard = NULL;//及时置空
return head;//返回新的头指针
}
? 对美团安全团队来说引入领先的安全技术设计能力构建全方位、多维度智能防御体...
Redis作为内存数据库,拥有非常高的性能,单个实例的QPS能够达到10W左右。但我们...
下面给出4个函数,足够你抵挡一切SQL注入漏洞!读懂代码,你就能融会贯通。 注意...
因为短日期不足2位,所以在网页排版的时候,影响美观,下面两个函数可以解决这个...
简单地一句话总结: 1.假如你想帮他尽快找个活儿,赚到钱,推荐PHP。 2.假如你想...
前言 大家都知道反射伤性能,但不得不反射的时候又怎么办呢?当真的被问题逼迫的...
由于自己疏忽,导致请求错误405,然后前端数据传输没错,百度大都说跟post提交方...
迎面走来了一个风尘仆仆的身穿格子衫的男子,手里拿着一个MacBook Pro,看着那稀...
点赞再看养成习惯微信搜索【 三太子敖丙 】关注这个好像有点东西的傻瓜 本文 Git...
本文告诉大家如何在 dotnet core 获取 Mac 地址 因为在 dotnetcore 是没有直接和...