移除链表元素
原题链接:力扣
给你一个链表的头节点 head
和一个整数 val
,请你删除链表中所有满足 Node.val == val
的节点,并返回新的头节点 。
方法一:原地删除节点
思路:
首先,定义两个指针:prve和cur。它们会在遍历链表的过程中分别指向当前节点的前一个节点和当前节点。初始情况下,prve指向NULL(因为当前节点是头结点),cur指向head。
然后,我们使用while循环遍历链表,直到cur指向NULL(也就是遍历完整个链表)。在每个节点处,我们判断当前节点(cur)的值是否等于val。如果是,我们就需要将该节点从链表中移除。
如果当前节点cur是头结点,那么我们需要特殊处理,因为头结点没有前一个节点。此时,我们修改head指向cur的下一个节点,然后释放cur所指向的内存空间,使得cur指向新的头结点(即head),继续遍历整个链表。
如果当前节点cur不是头结点,那么我们需要将cur从链表中移除。此时,我们将prve的next指针指向cur的下一个节点,然后释放cur所指向的内存空间,使得cur指向prve的下一个节点(也就是新的当前节点),继续遍历整个链表。
如果当前节点cur的值不等于val,我们就只需要更新prve和cur的指向,使得它们分别指向当前节点的前一个节点和当前节点的下一个节点,然后继续遍历整个链表。
具体过程图解:
需要注意头节点的值是val的情况
代码:
struct ListNode* removeElements(struct ListNode* head, int val)
{
//定义两个指针:prve和cur
struct ListNode* prve = NULL;
struct ListNode* cur = head;
while (cur != NULL)
{
//判断当前节点(cur)的值是否等于val。如果是,我们就需要将该节点从链表中移除
if (cur->val == val)
{
//如果当前节点cur是头结点,那么我们需要特殊处理
if (cur == head)
{
head = cur->next;
free(cur);
cur = head;
}
else
{
prve->next = cur->next;
free(cur);
cur = prve->next;
}
}
//如果当前节点cur的值不等于val,我们就只需要更新prve和cur的指向
else
{
prve = cur;
cur = cur->next;
}
}
return head;
}
方法二:遍历链表,把不是val的节点拿出来进行尾插到新链表
下面有两种方式来实现;
不带哨兵卫头节点:
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* tail = NULL;
struct ListNode* cur = head;
head = NULL;
while (cur)
{
if (cur->val != val)
{
if (tail == NULL)
{
head = tail = cur;
}
else
{
tail->next = cur;
tail = cur;
}
cur = cur->next;
}
else
{
struct ListNode* del = cur;
cur = cur->next;
free(del);
}
}
if (head)
{
tail->next = NULL;
}
return head;
}
带哨兵卫头节点:文章来源:https://www.toymoban.com/news/detail-507860.html
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* tail = NULL;
struct ListNode* cur = head;
head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
head->next = NULL;
while (cur)
{
if (cur->val != val)
{
tail->next = cur;
tail = cur;
cur = cur->next;
}
else
{
struct ListNode* del = cur;
cur = cur->next;
free(del);
}
}
if (head)
{
tail->next = NULL;
}
struct ListNode* del = head;
head = head->next;
free(del);
return head;
}
带哨兵卫头节点和不带哨兵卫头节点的方法类似。文章来源地址https://www.toymoban.com/news/detail-507860.html
到了这里,关于【数据结构OJ题】移除链表元素的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!