当前位置: 首页 > 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;策略模式使得算法可以独立于使用它的客户端…...

Android与SpringBoot的轻量级数据桥梁——OkHttp3实战解析

1. OkHttp3与SpringBoot的黄金组合 第一次用OkHttp3对接SpringBoot后端时&#xff0c;我盯着满屏的404错误差点崩溃。后来才发现&#xff0c;原来是因为手机和电脑不在同一个WiFi下。这种看似低级的错误&#xff0c;恰恰是新手最容易踩的坑。OkHttp3作为Android端最流行的网络请…...

Go的interface空值与类型断言的最佳实践

Go语言中的interface空值与类型断言是开发者经常遇到的核心概念&#xff0c;掌握其最佳实践能显著提升代码的健壮性和可维护性。interface的灵活性使其成为Go多态的重要工具&#xff0c;但空值处理和类型断言的不当使用可能导致运行时错误或逻辑漏洞。本文将深入探讨如何高效处…...

MCU开发 —— GD32篇:SEGGER Embedded Studio 外链编译器实战指南

1. 为什么选择SEGGER Embedded Studio开发GD32 SEGGER Embedded Studio&#xff08;简称SES&#xff09;作为一款轻量级跨平台IDE&#xff0c;这几年在嵌入式开发圈子里口碑相当不错。我自己从Keil转过来用SES开发GD32系列MCU已经两年多了&#xff0c;最直观的感受就是编译速度…...

HG-ha/MTools行业实践:短视频工作室AI配音+自动字幕+封面图生成闭环

HG-ha/MTools行业实践&#xff1a;短视频工作室AI配音自动字幕封面图生成闭环 你是不是也遇到过这样的场景&#xff1f;作为短视频工作室的创作者&#xff0c;每天都要面对海量的视频素材。一条1分钟的视频&#xff0c;从剪辑、配音、加字幕到制作封面&#xff0c;前前后后可能…...

提升数据抓取效率:用快马AI生成openclaw命令自动化脚本模板

最近在做一个数据抓取项目时&#xff0c;发现手动写openclaw命令实在太费时间了。每次都要重复写类似的fetch和parse命令&#xff0c;还要处理各种异常情况。后来发现用InsCode(快马)平台可以快速生成自动化脚本模板&#xff0c;效率提升了好几倍。今天就把这个经验分享给大家。…...

别再为GEO数据注释发愁了!三种方法(TXT/Soft/R包)保姆级代码实战

GEO数据注释实战指南&#xff1a;TXT/Soft/R包三种方法全解析 刚接触生物信息学的研究者常常会在GEO数据分析的第一步就卡壳——面对五花八门的注释文件格式&#xff0c;如何准确高效地将探针ID转换为基因Symbol&#xff1f;这个问题看似简单&#xff0c;实则暗藏玄机。我曾见过…...

微信毕业设计基于微信小程序的易物小店交换系统

前言 Spring Boot 易物小店交换系统是一个基于 Web 的应用程序&#xff0c;利用 Spring Boot 框架构建&#xff0c;主要用于帮助用户实现物品交换的功能。该系统为用户提供了一个便捷、安全、高效的平台&#xff0c;让他们能够轻松地发布自己想要交换的物品信息&#xff0c;寻找…...

3步解决AEUX图层对齐问题的完整指南

3步解决AEUX图层对齐问题的完整指南 【免费下载链接】AEUX Editable After Effects layers from Sketch artboards 项目地址: https://gitcode.com/gh_mirrors/ae/AEUX AEUX作为连接设计工具与After Effects的桥梁&#xff0c;是设计师实现高效工作流的关键。然而在实际…...

5分钟教程:让90年代经典游戏在Windows 11上完美运行的终极方案

5分钟教程&#xff1a;让90年代经典游戏在Windows 11上完美运行的终极方案 【免费下载链接】DDrawCompat DirectDraw and Direct3D 1-7 compatibility, performance and visual enhancements for Windows Vista, 7, 8, 10 and 11 项目地址: https://gitcode.com/gh_mirrors/d…...

如何快速掌握B站视频下载:DownKyi面向新手的终极教程

如何快速掌握B站视频下载&#xff1a;DownKyi面向新手的终极教程 【免费下载链接】downkyi 哔哩下载姬downkyi&#xff0c;哔哩哔哩网站视频下载工具&#xff0c;支持批量下载&#xff0c;支持8K、HDR、杜比视界&#xff0c;提供工具箱&#xff08;音视频提取、去水印等&#x…...