Leetcode_203.移除链表元素—C语言

简介: Leetcode_203.移除链表元素—C语言

❣️1.题目❣️


给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。


示例 1:

image.png

输入: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 <= 50
  • 0 <= val <= 50

❣️2.解答❣️


💞方法一:暴力法

算法思路:

image.png



遍历链表,如果当前节点的值等于val,则删除该节点,并且修改前驱节点的next指针指向后继节点。如果当前节点的值不等于val,则将前驱节点指向当前节点,当前节点指向下一个节点。


具体实现:


使用两个指针prev和cur,分别指向前驱节点和当前节点。开始遍历前,先初始化prev为NULL,cur为head,即第一个节点。然后进行while循环,当cur指向NULL时停止。在循环中,如果cur指向的节点的值等于val,则删除该节点,将后继节点指针保存在next中。如果prev不为NULL,则修改prev的next指针指向next;否则,说明删除的是头节点,直接修改head为next。最后,将cur指向next,继续下一轮循环。如果cur指向的节点的值不等于val,则将prev指向cur,cur指向下一个节点。最后,返回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;
    else
    head = next;
    cur = next;
  }
  else
  {
    prev = cur;
    cur = cur->next;
  }
  }
  return head;
}

💞方法二: 尾插法

首先定义了三个指针:newhead、tail 和 cur,其中 newhead 和 tail 用于构建新的链表,cur 用于遍历原链表。初始时,newhead 和 tail 都指向 NULL,cur 指向原链表的头结点 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,*tail=NULL;
struct ListNode*cur =head;
while(cur)
{
//不是val的节点取下来尾插
if(cur->val !=val)
{
//尾插
if(tail ==NULL)
newhead =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;
}

💞方法三:哨兵位法

首先定义一个哨兵位,作为新链表的头节点,同时也是一个尾指针,用于删除操作后将尾部节点的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;
相关文章
|
3天前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
7天前
|
存储 SQL 算法
LeetCode 83题:删除排序链表中的重复元素【面试】
LeetCode 83题:删除排序链表中的重复元素【面试】
|
7天前
|
存储 SQL 算法
LeetCode 题目 82:删除排序链表中的重复元素 II
LeetCode 题目 82:删除排序链表中的重复元素 II
|
7天前
|
SQL 算法 数据可视化
Leetcode27题:移除元素【27/1000 python】
Leetcode27题:移除元素【27/1000 python】
|
11天前
|
C语言
C语言学习记录——鹏哥二分法查找数组中元素 复习整理
C语言学习记录——鹏哥二分法查找数组中元素 复习整理
6 0
|
11天前
|
存储
数据结构——双向链表(C语言版)
数据结构——双向链表(C语言版)
10 2
|
11天前
|
算法 C语言
数据结构——单向链表(C语言版)
数据结构——单向链表(C语言版)
13 2
|
11天前
|
算法 搜索推荐 Java
【经典算法】LeetCode 215. 数组中的第K个最大元素(Java/C/Python3实现含注释说明,Medium)
【经典算法】LeetCode 215. 数组中的第K个最大元素(Java/C/Python3实现含注释说明,Medium)
9 3
|
17天前
|
存储 C语言 Python
|
7天前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表