【链表OJ 1】移除链表元素val

这篇具有很好参考价值的文章主要介绍了【链表OJ 1】移除链表元素val。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

        大家好,欢迎来到我的博客,此题是关于链表oj的第一题,此后还会陆续更新博客,如有错误,欢迎大家指正。

来源:https://leetcode.cn/problems/remove-linked-list-elements/description/

题目:

【链表OJ 1】移除链表元素val,C--数据结构刷题,数据结构,链表,c语言,笔记,vscode

方法一:定义prev和cur指针(双指针)

分析:

        使用两个指针prevcur来遍历链表。prev指针指向当前节点的前一个节点,而cur指针指向当前节点。

在 while 循环中,首先检查当前节点的值是否等于val。如果相等,则需要移除该节点。

如果当前节点的值不等于val,则将prev更新为cur, cur 更新为下一个节点,以继续遍历链表。

思路一:prev不为NULL

  • 如果 prev 不为 NULL,表示当前节点不是头节点,则将 prev->next 指向当前节点的下一个节点,然后释放当前节点 cur 的内存,并更新cur为 prev->next ,即下一个要检查的节点。

【链表OJ 1】移除链表元素val,C--数据结构刷题,数据结构,链表,c语言,笔记,vscode

思路二: prev 为 NULL

  • 如果 prev 为 NULL,表示当前节点是头节点,则将 cur 更新为头节点的下一个节点,释放头节点 head 的内存,并更新 head 为新的头节点 cur

【链表OJ 1】移除链表元素val,C--数据结构刷题,数据结构,链表,c语言,笔记,vscode

最后,返回更新后的链表头指针 head

该代码的目的是移除链表中所有值为 val 的节点,同时释放相应的内存。

代码实现: 

struct ListNode* removeElements(struct ListNode* head, int val)
{
	struct ListNode* prev = NULL, * cur = head;
	while (cur)
	{
		if (cur->val == val)
		{
			if (prev)
			{
				prev->next = cur->next;
				free(cur);
				cur = prev->next;
			}
			else
			{
				cur = head->next;
				free(head);//会把指针域next给free掉,因为它也是结构体的成员
				head = cur;
			}
		}
		else
		{
			prev = cur;
			cur = cur->next;
		}
	}
	return head;
}

执行:

【链表OJ 1】移除链表元素val,C--数据结构刷题,数据结构,链表,c语言,笔记,vscode

方法二:链表尾插

大致思路:

移除链表中所有值为val的节点,并使用尾插法构建一个新的链表,返回新链表的头指针。原始链表中不满足条件的节点会被保留,而满足条件的节点会被移除并释放内存。

尾插的思路:

函数使用三个指针cur、newhead 和 tail 来遍历和构建新的链表。

在 while 循环中,首先检查当前节点的值是否等于 val 。如果不等于 val ,则执行尾插操作将该节点添加到新链表中。

顺序:

  1. 如果 tail 为 NULL,表示当前节点是新链表的第一个节点。将newhead和 tail 都指向当前节点cur
  2. 接着,将 cur 更新为下一个节点,并将 tail->next 设置为 NULL,确保新链表断开
  3. 此时 tail 不为 NULL,表示当前节点需要添加到新链表的尾部。将 tail->next 指向当前节点 cur ,然后更新 tail 为 tail->next,新链表链接起来实现尾插。
  4. 接着持续2的操作

如果当前节点的值等于 val ,则需要移除该节点。将 cur 更新为下一个节点,并释放当前节点 del 的内存。

最后,返回新链表的头指针 newhead

画图:

【链表OJ 1】移除链表元素val,C--数据结构刷题,数据结构,链表,c语言,笔记,vscode

代码实现:

//尾插
struct ListNode* removeElements(struct ListNode* head,int val)
{
  struct ListNode*cur=head;
  struct ListNode *newhead=NULL,*tail=NULL;
 while(cur)
{
    if(cur->val!=val)
    {
      if(tail==NULL)
        {
			newhead=tail=cur;
		}
    	else
		{
     	    tail->next=cur;
     		tail=tail->next;
		}
     		cur=cur->next;//  这两条语句不可以调换顺序,否则tail->next=null
		 	tail->next=NULL;//cur=cur->next,这样写的话会尾插失败
		}
     else
	{
       struct ListNode*del=cur;
       cur=cur->next;
       free(del);//会把指针域next给free掉,因为它也是结构体的成员
	}
 }
 		return newhead;
 }

代码执行:

【链表OJ 1】移除链表元素val,C--数据结构刷题,数据结构,链表,c语言,笔记,vscode

         好了博客就分享到这里了,感谢你的来访!文章来源地址https://www.toymoban.com/news/detail-633549.html

到了这里,关于【链表OJ 1】移除链表元素val的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 单链表相关经典算法OJ题:移除链表元素

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 目录 前言 题目:移除链表元素 解法一: 解法一的代码实现: 解法二: 解法二代码的实现: 总结 世上有两种耀眼的光芒,一种是正在升起的太阳,一种是正在努力学习编程的你!一个爱学编程的人。各

    2024年02月04日
    浏览(47)
  • 数据结构c语言版:顺序表oj题练习(原地移除元素、合并两个有序数组)

    在单数组里面历遍找val,如果是val,就删除。不是就跳过。 时间复杂度O(n^2),最坏情况每个都是val。相当于一个等差数列。 比如 下标0开始找,0不是,不动数组 下标1,1不是,不动数组 下标2,2是,删除元素,变成【0,1,2,3,0,4,2】 下标2,2是,删除元素,变成【0,

    2024年01月23日
    浏览(63)
  • 203.移除链表元素

    循环遍历整个链表 定义两个指针:prev,cur 如果cur是要删除的节点,prev-cur-next,然后free(cur) 但是注意每次都要新定义一个节点del,用来free,不影响原来的cur节点往下循环 更新cur和prev 但是需要注意如果删除的是头节点,就要特殊处理,画图带上指针,情况分析,一目了然。

    2024年01月22日
    浏览(41)
  • 移除链表元素

    ☃️个人主页:fighting小泽 🌸作者简介:目前正在学习C语言和数据结构 🌼博客专栏:leetcode练习题 🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪🏻 题目链接: 移除链表元素 给你一个链表的头节点 head 和一个整数 val ,请你 删除链表中所有满足 Node.val == val 的节点 , 并返

    2024年02月04日
    浏览(40)
  • 移除链表元素详解

      原题出处: . - 力扣(LeetCode) 我们可以新创建一个链表,然后将不等于val的节点拿下来进行尾插,这样的方式更加简易,只需要遍历整个链表即可。 我们首先使用一个指针cur来遍历原链表,来获取不等于val的节点。 如果cur的next等于val就跳过这个节点,如果不等于val就尾

    2024年04月26日
    浏览(42)
  • 算法刷题-链表-移除链表元素

    链表操作中,可以使用原链表来直接进行删除操作,也可以设置一个虚拟头结点再进行删除操作,接下来看一看哪种方式更方便。 力扣题目链接 题意:删除链表中等于给定值 val 的所有节点。 示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 示例 2: 输入:head = [],

    2024年02月08日
    浏览(50)
  • Java移除链表元素

    目录 1.题目描述 2.题解 题解1 题解2 给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足  Node.val == val  的节点,并返回  新的头节点  。 示例 输入:head = [1,2,6,3,4,5,6],val = 6 输出:[1,2,3,4,5] 输入:head = [], val = 1 输出:[] 输入:head = [7,7,7,7], val = 7 输出:

    2024年02月07日
    浏览(30)
  • 移除链表元素 , 设计链表 ,反转链表

    leetcode 删除链表中等于给定值 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 输出:[] 移除元素  主要是  找到要移除的前一个  , 之后才能移除 。采用虚拟头节点的方法

    2024年02月08日
    浏览(42)
  • 【LeetCode】203. 移除链表元素

    leetcode链接 203. 移除链表元素

    2024年01月18日
    浏览(40)
  • LEEDCODE 203移除链表元素

    2024年02月06日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包