郑州房地产网站,建立网站数据库实验报告,北京广告有限公司,网络维护好学吗目录
❣️1.题目❣️
❣️2.解答❣️
#x1f49e;方法一#xff1a;暴力法
#x1f49e;方法二#xff1a; 尾插法
#x1f49e;方法三#xff1a;哨兵位法 ❣️1.题目❣️
给你一个链表的头节点 head 和一个整数 val #xff0c;请你删除链表中所有满足 Node.va…目录
❣️1.题目❣️
❣️2.解答❣️
方法一暴力法
方法二 尾插法
方法三哨兵位法 ❣️1.题目❣️
给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。 示例 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
输出[]提示
列表中的节点数目在范围 [0, 104] 内1 Node.val 500 val 50 ❣️2.解答❣️
方法一暴力法
算法思路 遍历链表如果当前节点的值等于val则删除该节点并且修改前驱节点的next指针指向后继节点。如果当前节点的值不等于val则将前驱节点指向当前节点当前节点指向下一个节点。
具体实现
使用两个指针prev和cur分别指向前驱节点和当前节点。开始遍历前先初始化prev为NULLcur为head即第一个节点。然后进行while循环当cur指向NULL时停止。在循环中如果cur指向的节点的值等于val则删除该节点将后继节点指针保存在next中。如果prev不为NULL则修改prev的next指针指向next否则说明删除的是头节点直接修改head为next。最后将cur指向next继续下一轮循环。如果cur指向的节点的值不等于val则将prev指向curcur指向下一个节点。最后返回head指针。
需要注意的是在删除节点后需要使用free函数释放该节点的内存空间。
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* prev NULL;struct ListNode* cur head;//while(cur !NULL)while (cur){if (cur-val val){struct ListNode* next cur-next;free(cur);if (prev)prev-next next;elsehead next;cur next;}else{prev cur;cur cur-next;}}return head;
}
方法二 尾插法
首先定义了三个指针newhead、tail 和 cur其中 newhead 和 tail 用于构建新的链表cur 用于遍历原链表。初始时newhead 和 tail 都指向 NULLcur 指向原链表的头结点 head。
然后进入 while 循环循环条件为 cur 不为 NULL。在循环体中首先判断 cur 的值是否等于 val如果等于说明需要删除该节点因此先将该节点的空间释放然后将 cur 指向下一个节点。如果不等于说明该节点需要保留因此将该节点从原链表中取下来并使用尾插法将其插入到新链表的尾部。具体地若 tail 为 NULL则说明此时新链表还没有节点因此将 newhead 和 tail 都指向当前节点否则将当前节点插入到 tail 的后面并更新 tail 指向新的尾节点。最后 cur 指向下一个节点继续进行循环。
当循环结束时所有不等于 val 的节点都已经被插入到了新链表中。此时需要检查一下 tail 是否为空如果不为空则将 tail 的 next 指针置为 NULL表示新链表的最后一个节点已经插入完毕。最后返回新链表的头结点 newhead。 struct ListNode*removeElements(struct ListNode* head,int val)
{
struct ListNode*newhead NULL,*tailNULL;
struct ListNode*cur head;
while(cur)
{
//不是val的节点取下来尾插
if(cur-val !val)
{
//尾插
if(tail NULL)
newhead tail cur;
else
{
tail-next cur;
tailtail-next;
}
cur cur-next;
}
else
{
struct ListNode*tmp cur;
cur cur-next;
free(tmp);
}
}
if(tail)
tail-next NULL;
return newhead;
}
方法三哨兵位法
首先定义一个哨兵位作为新链表的头节点同时也是一个尾指针用于删除操作后将尾部节点的next指针置为NULL。
接下来遍历链表如果当前节点的值不是val则将其从原链表取下来尾插到新链表中如果当前节点的值是val则将其从原链表中删除。
最后将哨兵位删除返回新链表的头节点即可。 struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* newhead NULL,*tail NULL;
struct ListNode* cur head;
// 哨兵位
newhead tail (struct ListNode*)malloc(sizeof(struct ListNode));
while(cur)
{
// 不是va1的节点取下来尾插
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;
}
