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

【数据结构】_链表经典算法OJ(力扣版)

目录

1. 移除链表元素

1.1 题目描述及链接

1.2 解题思路

1.3 程序

2. 反转链表

2.1 题目描述及链接

2.2 解题思路

2.3 程序

3. 链表的中间结点

3.1 题目描述及链接

3.2 解题思路

3.3 程序


1. 移除链表元素

1.1 题目描述及链接

原题链接:203. 移除链表元素 - 力扣(LeetCode)

题目描述:给你一个链表的头节点 head 和一个整数 val ,

请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。

1.2 解题思路

思路1:创建一个新链表,遍历原链表,将 Node.val != val的结点均尾插到新链表中。

思路2:创建链表结点curNode遍历链表,并对应记录该结点的前驱结点与后继结点,删除该结点后再对其余结点进行链接。

1.3 程序

以思路1为例:

1、创建新链表首先定义一个结点作为新链表的头结点newHead,且须作为方法的返回值返回;

2、遍历原链表判断当前结点的val值,需定义一个结构体指针curNode用于遍历原链表。

3、由于需将Node.val !=val的结点尾插至新链表,故需定义结构体指针变量newTail指向新链表的最后一个结。并在最后完成尾插后将newTail的后继指针域置为NULL

4、考虑特殊情况及相应处理:

(1)原链表为空:即head=NULL,导致curNode=NULL,不会进入第一个while循环,但在newTail->next=NULL 时会导致空指针解引用操作,出现错误。故需对newTail是否为空进行单独讨论处理。

(2)新链表为空:即原链表所有结点数据域的值都等于val,导致newTail->next=NULL 时会导致空指针解引用操作,出现错误。同(1):需对newTail是否为空进行单独讨论处理

处理逻辑为:

若newTail为空,再newTail->next=NULL,否则直接返回newHead(newHead也为空)

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {// 创建一个空链表ListNode* newHead=NULL;ListNode* newTail=NULL;ListNode* curNode=head;while(curNode){if(curNode->val!=val){// 情况1:链表为空if(newHead==NULL){newHead=curNode;newTail=curNode;}// 情况2:链表不为空else{newTail->next=curNode;newTail=newTail->next;}}curNode=curNode->next;}// 将新链表尾结点的后继指针置空// 讨论新链表为空与非空的两种情况if(newTail){newTail->next=NULL;}return newHead;
}

2. 反转链表

2.1 题目描述及链接

题目链接:206. 反转链表 - 力扣(LeetCode)

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

2.2 解题思路

思路1:

创建一个新的链表,并定义头结点指针newHead和尾结点指针newNode,遍历原链表,依次取当前结点头插到新链表中。

思路2:

无需创建新链表,创建三个指针,用于逐个逆转指针指向。

2.3 程序

以思路2为例:

创建三个指针变量。初始情况下,令n1指向空,n2指向原链表的头结点,n3指向原链表头结点的下一个结点。

以n2作为修改当前指向结点的后继指针域指向的用于遍历的结构体指针,逐个翻转指针域指向。再令n1、n2、n3依次后移。

考虑最终情况,n3最先变为空指针,直至n2指向原链表的最后一个结点完成指针域的指向反转后,表示当前链表已完成反转操作,故循环条件为n2不为空。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {// 判空if(head==NULL){return head;}// 创建三个指针ListNode* n1=NULL;ListNode* n2=head;ListNode* n3=n2->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3)n3=n3->next;}return n1;
}

3. 链表的中间结点

3.1 题目描述及链接

题目链接:876. 链表的中间结点 - 力扣(LeetCode)

题目描述:

给你单链表的头结点 head ,请你找出并返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。

3.2 解题思路

思路1:

遍历原链表,使用count计数,count/2位置结点的下一个结点就是满足条件的中间结点,可返回count/2位置结点的后继指针即可。

思路2:快慢指针

创建两个结构体指针变量,令一个指针每次走一步,另外一个指针每次走两步,走得快的指针称为fast快指针,走得慢的指针称为slow慢指针。

3.3 程序

以思路二为例:考虑循环条件。

对于奇数个结点的链表,当fast->next=NULL时,slow正指向中间结点;

对于偶数个结点的链表,当fast=NULL时,slow正指向两个中间结点的后一个节点;

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {ListNode* slow=head;ListNode* fast=head;while(fast!=NULL&&fast->next!=NULL){fast=fast->next->next;slow=slow->next;}return slow;
}

注:对于循环条件while(fast!=NULL&&fast->next!=NULL)不可更改为

while(fast->next!=NULL&&fast!=NULL),由于在偶数个结点的链表中,当fast==NULL时,slow正指向两个中间结点的后一个,此种情况下,若交换顺序则会导致对空指针的解引用,出错。

由于逻辑与具有短路特性,若已验证操作符左侧表达式为假,则不再验右侧表达式真假。

相关文章:

【数据结构】_链表经典算法OJ(力扣版)

目录 1. 移除链表元素 1.1 题目描述及链接 1.2 解题思路 1.3 程序 2. 反转链表 2.1 题目描述及链接 2.2 解题思路 2.3 程序 3. 链表的中间结点 3.1 题目描述及链接 3.2 解题思路 3.3 程序 1. 移除链表元素 1.1 题目描述及链接 原题链接:203. 移除链表…...

【Linux】统计文本中每行指定位置出现的字符串的次数

统计文本中每行指定位置出现的字符串的次数 假定情景 某些项目,会把某个特定事件记录到Log中并且落盘(保持到硬盘)。基于落盘后的日志,要统计这些日志里产生该特定事件的次数 统计脚本 可以写一个sh脚本,来解析某个…...

【赵渝强老师】K8s中Pod探针的ExecAction

在K8s集群中,当Pod处于运行状态时,kubelet通过使用探针(Probe)对容器的健康状态执行检查和诊断。K8s支持三种不同类型的探针,分别是:livenessProbe(存活探针)、readinessProbe&#…...

商品信息管理自动化测试

目录 前言 一、思维导图 二、代码编写 1.在pom.xml文件中添加相关依赖 2.自动化代码编写 三、代码测试 小结 前言 1. 针对商品信息管理项目进行测试,商品信息管理项目主要有商品列表页、部门列表页、员工列表页,主要功能:对商品信息的…...

Redis实战(黑马点评)——redis存储地理信息、位图、HyperLogLog 用法

Redis存储geo数据类型基本介绍 geo 就是 geolocation 的简写形式,代表地理坐标。redis 在 3.2 版本中加入了对 geo 的支持,允许存储地理坐标信息,帮助我们根据经纬度来检索数据。常见的命令有: geoadd:添加一个地理空…...

判断1到100之间有多少个素数,并输出所有的素数。

def is_prime(num): #判断一个数是否素数if num<1:return False #因为1和负数都不是素数for i in range(2,int(num**0.5)1): #从2开始到根号num的整数结束&#xff0c;因为一个数num不是素数&#xff0c;那么把必定有一个小于或等于根号num的因素if num%i0:return False #如…...

JAVA:利用 Content Negotiation 实现多样式响应格式的技术指南

1、简述 Content Negotiation&#xff08;内容协商&#xff09; 是 RESTful 服务的重要特性&#xff0c;允许客户端和服务器根据请求的不同特性动态选择适合的响应格式。它是一种在 HTTP 协议中实现的机制&#xff0c;通过它&#xff0c;服务器能够根据客户端需求返回适合的内…...

layui Table单元格编辑支持Enter键换行,包括下拉框单元格

layui Table表格编辑支持Enter键换行 可编辑单元格 $(".layui-table td").keydown(function (e) {// console.log("111",e);var index $(this).index(),tr $(this).parent(tr),isKeydown (event.type "keydown");if (e.code "Enter&q…...

Swoole的MySQL连接池实现

在Swoole中实现MySQL连接池可以提高数据库连接的复用率&#xff0c;减少频繁创建和销毁连接所带来的开销。以下是一个简单的Swoole MySQL连接池的实现示例&#xff1a; 首先&#xff0c;确保你已经安装了Swoole扩展和PDO_MySQL扩展&#xff08;或mysqli&#xff0c;但在这个示…...

无人机红外热成像:应急消防的“透视眼”

无人机红外热成像&#xff1a;应急消防的“透视眼” 亲爱的小伙伴们&#xff0c;每年一到夏天&#xff0c;应急消防的战士们就像上紧了发条的闹钟&#xff0c;时刻准备应对各种灾害。炎热天气让火灾隐患“蹭蹭”往上涨&#xff0c;南北各地还有防洪救灾、台风、泥石流等灾害轮…...

【redis】Redis操作String类型key的发生了什么?

关于Redis操作&#xff08;添加、删除、修改、查询&#xff09;String类型key的完整过程&#xff0c;包括引用源码数据、时序图、磁盘IO读写、数据长度限制和故障处理机制。 数据结构 Redis对象&#xff08;robj&#xff09; typedef struct redisObject {unsigned type:4; …...

hdfs之读写流程

写入流程&#xff1a; 客户端Client想将文件a.txt上传至hdfs&#xff0c;首先向Namenode发送请求进行权限校验&#xff0c;Namenode通过后会计算出来三个节点&#xff0c;并将这三个节点告知客户端&#xff0c;客户端将输入进行切割成块&#xff0c;一个一个的块进行传输&…...

研发的立足之本到底是啥?

0 你的问题&#xff0c;我知道&#xff01; 本文深入T型图“竖线”的立足之本&#xff1a;专业技术 技术赋能业务能力。研发在学习投入精力最多&#xff0c;也误区最多。 某粉丝感发展遇到瓶颈&#xff0c;项目都会做&#xff0c;但觉无提升&#xff0c;想跳槽。于是&#x…...

Baklib揭示内容中台与人工智能技术的创新协同效应

内容概要 在当今信息爆炸的时代&#xff0c;内容的高效生产与分发已成为各行业竞争的关键。内容中台与人工智能技术的结合&#xff0c;为企业提供了一种新颖的解决方案&#xff0c;使得内容创造的流程更加智能化和高效化。 内容中台作为信息流动的核心&#xff0c;能够集中管…...

智慧消防营区一体化安全管控 2024 年度深度剖析与展望

在 2024 年&#xff0c;智慧消防营区一体化安全管控领域取得了令人瞩目的进展&#xff0c;成为保障营区安全稳定运行的关键力量。这一年&#xff0c;行业在政策驱动、技术创新应用、实践成果及合作交流等方面呈现出多元且深刻的发展态势&#xff0c;同时也面临着一系列亟待解决…...

自定义数据集,使用 PyTorch 框架实现逻辑回归并保存模型,然后保存模型后再加载模型进行预测

在本文中&#xff0c;我们将展示如何使用 NumPy 创建自定义数据集&#xff0c;利用 PyTorch 实现一个简单的逻辑回归模型&#xff0c;并在训练完成后保存该模型&#xff0c;最后加载模型并用它进行预测。 1. 创建自定义数据集 首先&#xff0c;我们使用 NumPy 创建一个简单的…...

UE5 特效

能帮到你的话&#xff0c;就给个赞吧 &#x1f618; 文章目录 post processexposurebloomvignettesaturationunbound material材质蓝图alt z base colorconstant3Vector roughnessconstant metallicconstant pbrroughnessmetallicmake more realmake some areas rougher than o…...

CMAKE工程编译好后自动把可执行文件传输到远程开发板

# 设置 CMake 最低版本要求 cmake_minimum_required(VERSION 3.10)# 设置项目名称 project(MyProject)# 添加可执行文件&#xff0c;这里以项目名作为可执行文件的名称 add_executable(${PROJECT_NAME} main.cpp)# 设置开发板信息 set(DEVELOPMENT_BOARD_IP "192.168.1.10…...

Windows 程序设计7:文件的创建、打开与关闭

文章目录 前言一、文件的创建与打开CreateFile1. 创建新的空白文件2. 打开已存在文件3. 打开一个文件时&#xff0c;如果文件存在则打开&#xff0c;如果文件不存在则新创建文件4.打开一个文件&#xff0c;如果文件存在则打开文件并清空内容&#xff0c;文件不存在则 新创建文件…...

策略模式 - 策略模式的使用

引言 在软件开发中&#xff0c;设计模式是解决常见问题的经典解决方案。策略模式&#xff08;Strategy Pattern&#xff09;是行为型设计模式之一&#xff0c;它允许在运行时选择算法的行为。通过将算法封装在独立的类中&#xff0c;策略模式使得算法可以独立于使用它的客户端…...

原神抽卡数据分析终极指南:genshin-wish-export完全使用教程

原神抽卡数据分析终极指南&#xff1a;genshin-wish-export完全使用教程 【免费下载链接】genshin-wish-export biuuu/genshin-wish-export - 一个使用Electron制作的原神祈愿记录导出工具&#xff0c;它可以通过读取游戏日志或代理模式获取访问游戏祈愿记录API所需的authKey。…...

STM32F103 SPI+DMA驱动WS2812B的时序实现原理

1. WS2812B_STM32_Libmaple 库深度解析&#xff1a;基于 SPI DMA 的高性能 NeoPixel 驱动实现WS2812B&#xff08;常被称作 NeoPixel&#xff09;是当前嵌入式系统中最主流的单线协议可寻址 RGB LED。其核心挑战在于严格的时序要求&#xff1a;T0H&#xff08;逻辑 0 的高电平时…...

虚拟机自动化新范式:CUA Computer SDK十分钟入门指南

虚拟机自动化新范式&#xff1a;CUA Computer SDK十分钟入门指南 【免费下载链接】cua Create and run high-performance macOS and Linux VMs on Apple Silicon, with built-in support for AI agents. 项目地址: https://gitcode.com/GitHub_Trending/cua/cua 在当今的…...

实时数据复制技术在大数据平台中的应用与实践

实时数据复制技术在大数据平台中的应用与实践关键词&#xff1a;实时数据复制、大数据平台、CDC&#xff08;变更数据捕获&#xff09;、数据同步、数据一致性、分布式系统、ETL摘要&#xff1a;本文深入探讨了实时数据复制技术在大数据平台中的核心应用场景与实践方法。我们将…...

安路PH1A180 FPGA实战:用米联客FDMA IP搞定DDR视频缓存,附源码调试心得

安路PH1A180 FPGA实战&#xff1a;FDMA IP与DDR视频缓存深度优化指南 在视频处理系统中&#xff0c;FPGADDR架构已成为实时高清视频流处理的标准方案。安路PH1A180凭借其高性能特性&#xff0c;配合米联客FDMA IP核&#xff0c;能够构建稳定高效的视频缓存系统。但在实际工程落…...

Android TTS自定义开发:从0到1打造专属语音引擎

Android TTS自定义开发&#xff1a;从0到1打造专属语音引擎 【免费下载链接】tts-server-android 这是一个Android系统TTS应用&#xff0c;内置微软演示接口&#xff0c;可自定义HTTP请求&#xff0c;可导入其他本地TTS引擎&#xff0c;以及根据中文双引号的简单旁白/对话识别朗…...

PyKitti终极指南:三步搞定KITTI自动驾驶数据处理

PyKitti终极指南&#xff1a;三步搞定KITTI自动驾驶数据处理 【免费下载链接】pykitti Python tools for working with KITTI data. 项目地址: https://gitcode.com/gh_mirrors/py/pykitti 你是否正在为复杂的KITTI数据集处理而头疼&#xff1f;面对激光雷达点云、立体相…...

Ruby OpenAI用户行为分析:AI交互模式深度研究

Ruby OpenAI用户行为分析&#xff1a;AI交互模式深度研究 【免费下载链接】ruby-openai OpenAI API Ruby! &#x1f916;&#x1fa75; Now with Assistants, Threads, Messages, Runs and Text to Speech &#x1f37e; 项目地址: https://gitcode.com/gh_mirrors/ru/ruby-…...

利用Python和快速傅里叶变换解析振动传感器数据:从趋势图到频谱分析的完整指南

1. 振动传感器数据分析入门指南 当你第一次拿到振动传感器采集的数据时&#xff0c;可能会被满屏的数字搞得一头雾水。别担心&#xff0c;我刚开始接触时也是这样。振动数据就像是一本用密码写成的日记&#xff0c;而Python和快速傅里叶变换(FFT)就是我们破译这些密码的神奇工具…...

[PTA]从汉诺塔到斐波那契:递归思想在经典算法问题中的实战解析

1. 递归思想&#xff1a;从神话到代码的魔法之旅 第一次接触递归时&#xff0c;我盯着汉诺塔的代码看了整整三小时。那种感觉就像小时候听魔术师说"见证奇迹的时刻"——明明看着他把鸽子变没了&#xff0c;却死活想不通机关在哪。递归就是编程世界最优雅的魔术&#…...