当前位置: 首页 > news >正文

【LeetCode】移除链表中等于设定值的元素、反转链表

主页:HABUO🍁主页:HABUO  

🌜有时候世界虽然是假的,但并不缺少真心对待我们的人🌛


1. 移除链表中设定值的元素

题目:给你一个链表的头节点 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                              输出:[]

分析:这是我们所做的第一道有关链表的题,当然了,属于简单题,唯一需要分析的就是,在链表中我们怎么进行迭代?至于删除元素我们在实现链表的时候,就已经实现了无论是头删尾删或者指定位置后删,所以这个题很容易解决,除了一些细节需要注意,具体思想见下图:

所以我们先定义一个cur指针指向我们所要删除的节点,但是我们还要访问上一个节点,这不是双向链表,因此我们还需要创建一个prev指针指向cur的前一个节点,因此如上所示的正常情况的代码如下:

if (cur->val == val)
{prev->next = cur->next;free(cur);cur = prev->next;
}
else
{prev = cur;cur = cur->next;
}

但会产生一个问题就是如果我们一上来就碰到我们所要删除的节点怎么办?因为此时prev指向的为NULL, prev->next就会对NULL解引用,造成错误,如下图所示,所以我们应该对起始位置加以控制。代码实现如下:

struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* cur = head;struct ListNode* prev = NULL;while (cur){if (cur->val == val){if (cur == head){head = cur->next;free(cur);cur = head;}else{prev->next = cur->next;free(cur);cur = prev->next;}}else{prev = cur;cur = cur->next;}}return head;
}

2.反转链表

题目:给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 

示例:

输入:head = [1,2,3,4,5]            输出:[5,4,3,2,1]

输入:head = [1,2]                     输出:[2,1]

输入:head = []                          输出:[]

分析:本题我们将通过两个方法去解决, 第一个方法是三指针法,为什么要用三个指针?其实也不难想,我们的主要思路不就是从第一个开始,把每个节点中所存储的下一个节点的地址都修改成该节点的上一个节点地址,但是下一个节点我该怎么找到,是不是就是内存泄漏了,因此我们需要拿个伪指针来指向它,同样的道理,我们这两个伪指针往前走一步了,但是改变的节点我们又该如何找到呢?是不是又没办法了,因此还需要一个伪指针,总体思路见下图:

主体代码实现如下:

cur->next = prev;
prev = cur;
cur = next;

这里需要注意,如果题中给的链表为空链表,或者只有一个节点,next是不是很容易就造成了对NULL进行解引用,所以,我们先不让next指向cur的下一个,刚开始让next和cur一同指向head,处理办法见下:

struct ListNode* prev = NULL;
struct ListNode* cur = head;
struct ListNode* next = head;
while (cur)
{if (cur == head){next = next->next;}cur->next = prev;prev = cur;cur = next;
}

到此还有一点我们没有注意到,到链表走到最后的时候我们循环控制条件是cur,也就意味着cur为NULL循环才停止,但此时的next怎么办?我们是不是还要处理一下,所以总体代码见下:

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* prev = NULL;struct ListNode* cur = head;struct ListNode* next = head;while (cur){if (cur == head){next = next->next;}cur->next = prev;prev = cur;cur = next;if (next != NULL)next = next->next;}return prev;
}

方法二:头插法, 这种方法的思想是借用我们对单链表实现的时候,对头插接口实现的思想的一个延用,就是建立一个新链表,把老链表进行释放掉,这样的一个思想我们只需要将题中所给的链表从前往后逐一的进行头插即可,主题思路见下图:

头插接口的实现我们在前边的单链表的实现的过程中已经涉及,不再详述,这里需要注意的就是我们释放原链表的时候,可以借用head,没必要再重新建立一个伪指针进行指向,head也是我们的一个形参依然可以用,所以代码实现如下:

struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
temp->val = cur->val;
temp->next = Newhead;
Newhead = temp;
cur = cur->next;
free(head);
head = cur;

 新链表的头指针我们是用Newhead进行维护,每新建立一个节点,到数值移植过去之后,都会将Newhead进行更新,因此最终返回Newhead即可,所以总代码如下:

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* Newhead = NULL;struct ListNode* cur = head;while (cur){struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));temp->val = cur->val;temp->next = Newhead;Newhead = temp;cur = cur->next;free(head);head = cur;}return Newhead;
}

🍁这世界上有各种各样的人,恰巧我们成为了朋友🍁

🌟这不是缘分,只仅仅是我们本就应该是朋友🌟

相关文章:

【LeetCode】移除链表中等于设定值的元素、反转链表

主页:HABUO🍁主页:HABUO 🌜有时候世界虽然是假的,但并不缺少真心对待我们的人🌛 1. 移除链表中设定值的元素 题目:给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所…...

Redis - 主从复制

在分布式系统中为了解决单点问题,通常会把数据复制多个副本部署到其他服务器,满⾜故障恢 复和负载均衡等需求。Redis也是如此,它为我们提供了复制的功能,实现了相同数据的多个Redis副 本。复制功能是⾼可⽤Redis的基础&#xff0c…...

UE5 HLSL 学习笔记

half的取值范围是整形的-60000 到 60000,考虑带宽的情况下使用half vector默认为float4 访问可以.xyzw,也可以.rgba,也可以[index],且顺序可以变,比如说.yzwx 矩阵的获取值的方式 第一个行代表获取第1行第0号元素 第…...

一个简单ASP.NET购物车设计

思路&#xff1a; 创建一个多选列表 在cs文件里初始化购物车会话变量,同&#xff0c;创建一个新的 List<string> 并将其赋值给会话状态中的 "Cart" 键–&#xff08;利用Session&#xff09; Session 是一种用于存储用户特定信息的对象&#xff0c;这些信息可…...

双向循环列表

双向循环列表的实现。 根据定义实现。不解释&#xff0c;具体细节看代码。 list.h #pragma once#pragma pack(1)typedef struct _MyListEntry {_MyListEntry* next;_MyListEntry* prev; }MyListEntry;#pragma pack()class MyListClass { public:MyListEntry* m_list0;int m_k…...

go项目出现了ambiguous import要怎么解决?

前言 最近小编在 构建一个项目时出现了问题&#xff0c;提示报错里ambiguous import&#xff1b;查询了解到是 依赖包存在多个不同版本的问题 这样的情况要怎么解决呢&#xff1f; 小编先是将问题抛给了 chatgpt&#xff0c;得到了如下的信息&#xff1a; # 清理缓存 go clea…...

更改Ubuntu22.04锁屏壁纸

更改Ubuntu22.04锁屏壁纸 sudo apt install gnome-shell-extensions gnome-shell-extension-manager安装Gnome Shell 扩展管理器后&#xff0c;打开“扩展管理器”并使用搜索栏找到“锁屏背景”扩展...

ROS2humble版本使用colcon构建包

colcon与与catkin相比&#xff0c;没有 devel 目录。 创建工作空间 首先&#xff0c;创建一个目录 ( ros2_example_ws ) 来包含我们的工作区: mkdir -p ~/ros2_example_ws/src cd ~/ros2_example_ws 此时&#xff0c;工作区包含一个空目录 src : . └── src1 directory, …...

CSRF 跨站请求伪造的实现原理和预防措施

CSRF&#xff08;跨站请求伪造&#xff09;概述 CSRF&#xff08;Cross-Site Request Forgery&#xff09;&#xff0c;即跨站请求伪造&#xff0c;是一种攻击手段&#xff0c;攻击者利用受害者在网站上已认证的身份信息&#xff0c;诱使受害者发起未经授权的请求&#xff0c;从…...

【LeetCode】【算法】22. 括号生成

LeetCode 22. 括号生成 题目描述 数字 n 代表生成括号的对数&#xff0c;请你设计一个函数&#xff0c;用于能够生成所有可能的并且 有效的 括号组合。 解题思路 天天到处看答案&#xff0c;看的灵神的解题思路回溯不会写&#xff1f;套路在此&#xff01;&#xff08;Pyth…...

WPF+MVVM案例实战与特效(二十五)- 3D粒子波浪效果实现

文章目录 1、案例效果2、案例实现1、文件创建2. 功能代码实现3、粒子功能应用1、前端布局与样式2、代码解释2、 后端功能代码1、案例效果 2、案例实现 1、文件创建 打开 Wpf_Examples 项目、Models 文件夹下创建 3D粒子模型类 ParticleWaveEffectModel.cs 文件。在Tools 文件…...

wsl2安装和使用

WSL(Windows Subsystem for Linux)是一个在 Windows 操作系统上运行 Linux 二进制可执行文件的兼容层。它允许用户在 Windows 上运行 Linux 命令行工具和应用程序。 主要功能 简化开发流程:开发者可以在 Windows 上使用 Linux 的开发工具链。兼容性:支持多种 Linux 发行版,…...

【划分型 DP-最优划分】【腾讯笔试压轴】【hard】力扣132. 分割回文串 II

给你一个字符串 s&#xff0c;请你将 s 分割成一些子串&#xff0c;使每个子串都是回文串。 返回符合要求的 最少分割次数 。 示例 1&#xff1a; 输入&#xff1a;s “aab” 输出&#xff1a;1 解释&#xff1a;只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子…...

Kubernetes-镜像加速篇-01-加速工具

[友情链接]加速三剑客 镜像加速&#xff1a;https://github.com/DaoCloud/public-image-mirror 二进制文件加速&#xff1a;https://github.com/DaoCloud/public-binary-files-mirror Helm 加速&#xff1a;https://github.com/DaoCloud/public-helm-charts-mirror 二进制文件…...

字母的异位数

做leetcode242题时出现了一个错误&#xff1a; bool isAnagram(string s, string t) {map<char,int> cnt;bool ans true;int lens s.length();int lent t.length();for(int i 0;i < lens;i){cnt[s[i]] 1;cout << cnt[s[i]] << endl;}for(int i 0;i…...

达梦数据库DM Exception字符串截断错误,略坑~

前言 我之前在使用达梦数据库的时候&#xff0c;遇到了很多很多的问题&#xff0c;主要对达梦数据库也不是很熟悉&#xff0c;它的语法和我所熟悉的mysql和postgresql有很大的区别。 今天&#xff0c;讲一下我之前遇到的一个问题。这个问题的起因是用达梦数据库迁移工具&…...

vue实现图片无限滚动播放

本人vue新手菜鸡&#xff0c;文章为自己在项目中遇到问题的记录&#xff0c;如有不足还请大佬指正 文章目录 实现效果代码展示总结 因为刚接触vue&#xff0c;本想着看看能不能用一些element的组件实现图片的轮播效果&#xff0c;尝试使用过element-UI里的走马灯Carouse&#x…...

python爬虫指南——初学者避坑篇

目录 Python爬虫初学者学习指南一、学习方向二、Python爬虫知识点总结三、具体知识点详解和实现步骤1. HTTP请求和HTML解析2. 正则表达式提取数据3. 动态内容爬取4. 数据存储5. 反爬虫应对措施 四、完整案例&#xff1a;爬取京东商品信息1. 导入库和设置基本信息2. 获取网页内容…...

Vivado+Vscode联合打造verilog环境

一、Vivado下载安装 详细参考我另一篇文章&#xff1a; Vivado2022.2下载安装_fpga vivado下载-CSDN博客https://blog.csdn.net/weixin_61081689/article/details/143460790?spm1001.2014.3001.5501 二、Vscode下载安装 详细参考我另一篇文章&#xff1a; VscodeAnacond…...

Python 微服务架构

Python 微服务架构 目录 &#x1f6e0; 微服务架构的基本概念与设计原则⚡ Python 在微服务中的应用&#xff08;Flask、FastAPI等框架&#xff09;&#x1f680; 微服务的自动化部署与运维&#x1f50d; 服务发现与负载均衡&#x1f4ca; 微服务中的日志集中管理与监控&…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...