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

【数据结构初阶】单链表经典算法题十二道——得道飞升(上篇)

目录

1、移除元素

2、反转链表

3、链表的中间节点

4、合并两个有序链表

Relaxing Time!!!

————————————————  天气之子·幻  ————————————————


1、移除元素

思路:

创建一个新链表(newhead,newtail),遍历原链表,把不等于 val 的结点尾插到新链表中。

/*** 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;ListNode* newtail;newhead=newtail=NULL;//遍历数组ListNode* pcur=head;while(pcur){if(pcur->val!=val){//又分两种情况,链表为空,不为空if(newhead==NULL){newtail=newhead=pcur;}else{newtail->next=pcur;newtail=newtail->next;}}pcur=pcur->next;}//[7,7,7,7,7],val=7 ,这种情况下,newtail=NULL,newtail->next=NULL,此时newtail不能解引用,所以加上if条件if(newtail)               newtail->next=NULL;return newhead;
}

注意:

当原链表为空时,newhead = newtail = pcur; 

在实例中,最后一个5结点被尾插到新链表中时,5结点的next指针指向的仍然是后面的6结点,所以最后返回的时候结果里面含有6,所以我们把最后一个等于val结点的next指针指向NULL即可!

2、反转链表

新奇思路:

/*** 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,*n2,*n3;n1=NULL;n2=head;n3=n2->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3)n3=n3->next;}return n1;
}

3、链表的中间节点

思路: 

奇数个结点

偶数个结点 

/*** 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->next&&fast)错误,不可互换顺序,当为偶数个结点时,fast==NULL循环结束,但是while循环内会先判断fast->next,空指针不能解引用,会报错while(fast&&fast->next){//慢指针每次走一步//快指针每次走两步slow=slow->next;fast=fast->next->next;}//此时slow指向的结点恰好是中间结点return slow;
}

快慢指针为什么可以找到中间结点?(快慢指针的原理)

慢指针每次走一步,快指针每次走两步,当快指针走到链表的尾结点时,假设链表的长度为n,快指针走的路程是慢指针的两倍,2*慢=快,即慢指针走的路程是n/2。

4、合并两个有序链表

思路:

创建一个新链表,newhead,newtail 指向新链表的头结点,定义两个指针分别指向原链表的头结点,两个指针指向的数据比较大小,谁小谁尾插到新链表里面。思路清晰,不过要注意很多细节,直接上代码:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {//处理原链表为空链表的情况if(list1==NULL){return list2;}if(list2==NULL){return list1;}//创建一个新链表ListNode* newhead=NULL;ListNode* newtail=NULL;//创建两个指针分别指向两个链表的头结点来遍历原链表ListNode* l1=list1;ListNode* l2=list2;while(l1&&l2){if(l1->val<l2->val){//l1尾插到新链表if(newtail==NULL){newtail=newhead=l1;}else{newtail->next=l1;newtail=newtail->next;}l1=l1->next;}else{//l2尾插到新链表if(newhead==NULL){newtail=newhead=l2;}else{newtail->next=l2;newtail=newtail->next;}l2=l2->next;}}//出循环,要么l1==NULL,要么l2==NULLif(l1)newtail->next=l1;  想想这里为啥不用while循环?if(l2)newtail->next=l2;return newhead;
}
//优化过后,申请一个不为空的链表,就无需再判断新链表是否为空,最后不要忘记free
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {//链表为空的情况if(list1==NULL){return list2;}if(list2==NULL){return list1;}//创建一个新链表ListNode* newhead,*newtail;newhead=newtail=(ListNode*)malloc(sizeof(ListNode));//定义两个指针来遍历数组ListNode* l1=list1;ListNode* l2=list2;while(l1&&l2){if(l1->val<l2->val){newtail->next=l1;l1=l1->next;newtail=newtail->next;}else{newtail->next=l2;l2=l2->next;newtail=newtail->next;}}if(l1)newtail->next=l1;if(l2)newtail->next=l2;ListNode* ret=newhead->next;free(newhead);newhead=NULL;return ret;}


完—

Relaxing Time!!!

——  天气之子·幻  ——

天气之子·幻_TypeD_高音质在线试听_天气之子·幻歌词|歌曲下载_酷狗音乐酷狗音乐为您提供由TypeD演唱的高清音质无损天气之子·幻mp3在线听,听天气之子·幻,只来酷狗音乐!icon-default.png?t=N7T8https://t4.kugou.com/song.html?id=b43Kh7aCPV2

至此结束——

再见——

相关文章:

【数据结构初阶】单链表经典算法题十二道——得道飞升(上篇)

目录 1、移除元素 2、反转链表 3、链表的中间节点 4、合并两个有序链表 Relaxing Time&#xff01;&#xff01;&#xff01; ———————————————— 天气之子幻 ———————————————— 1、移除元素 思路&#xff1a; 创建一个新链表&#xff0…...

Python爬虫技术 第16节 XPath

XPath是一种在XML文档中查找信息的语言&#xff0c;尽管XML和HTML在语法上有区别&#xff0c;但XPath同样适用于HTML文档的解析&#xff0c;尤其是在使用如lxml这样的库时。XPath提供了一种强大的方法来定位和提取XML/HTML文档中的元素和属性。 XPath基础 XPath表达式由路径表…...

本地部署,Whisper: 开源语音识别模型

目录 简介 特点 应用 使用方法 总结 GitHub - openai/whisper: Robust Speech Recognition via Large-Scale Weak SupervisionRobust Speech Recognition via Large-Scale Weak Supervision - openai/whisperhttps://github.com/openai/whisper 简介 Whisper 是一个由 O…...

history,hash缓存那些事

vue-router 中的 createWebHistory&#xff0c;createWebHashHistory两种模式 createWebHistory 是基于 window.history 对象是HTML5提供的用于维护当前标签页浏览历史的对象&#xff0c;主要功能是前进后退和在不刷新页面的情况下&#xff0c;修改地址栏里的URL地址。histor…...

Spring Boot的Web开发

目录 Spring Boot的Web开发 1.静态资源映射规则 第一种静态资源映射规则 2.enjoy模板引擎 3.springMVC 3.1请求处理 RequestMapping DeleteMapping 删除 PutMapping 修改 GetMapping 查询 PostMapping 新增 3.2参数绑定 一.支持数据类型: 3.3常用注解 一.Request…...

Spark 解析嵌套的 JSON 文件

1、什么是嵌套的JSON文件&#xff1f; 嵌套的JSON文件是指文件中包含了嵌套的JSON对象或数组。例如&#xff0c;以下是一个嵌套的JSON文件的示例&#xff1a; {"name": "John","age": 30,"address": {"street": "123…...

VMware虚拟机中CentOS7自定义ip地址并且固定ip

配置固定ip(虚拟机) 前提&#xff1a;虚拟机网络配置成&#xff0c;自定义网络并选择VMnet8(NAT 模式) 操作(如下图)&#xff1a;点击虚拟机–》设置–》–》硬件–》网络适配器–》自定义&#xff1a;特定虚拟网络–》选择&#xff1a;VMnet8(NAT 模式) 虚拟机网络设置 需要记…...

CCS(Code Composer Studio 10.4.0)编译软件中文乱码怎么解决

如果是所有文件都出现了中文乱码这时建议直接在窗口首选项中修改&#xff1a;选择"Window" -> "Preferences"&#xff0c;找到"General" -> "Workspace"&#xff0c;将"Text file encoding"选项设置为"Other&quo…...

Flutter 3 完全支持网页端

Flutter 3 可以用于开发网页端应用。自 Flutter 2.0 起&#xff0c;Flutter 就已经支持 Web 平台&#xff0c;并且在 Flutter 3 中得到了进一步的改进和优化。以下是使用 Flutter 3 开发网页端的一些优势和特点&#xff1a; Flutter 3 开发网页端的优势&#xff1a; 跨平台一致…...

vue.js入门

目录 一. 框架概述 二. vue常用命令 2.1 插值表达式 2.2 v-text 2.3 v-html 2.4 v-on 2.5 v-model 2.6 v-show 2.7 v-if 2.8 v-else 2.9 v-bind 2.10 v-for 三. vue生命周期函数 目录 一. 框架概述 二. vue常用命令 2.1 插值表达式 2.2 v-text 2.3 v-html 2…...

API签名认证

前言&#xff08;项目背景&#xff09;&#xff1a; 这个API签名认证是API开放平台得一个重要环节&#xff0c;我们知道&#xff0c;这个API开发平台&#xff0c;用处就是给客户去调用现成得接口来完成某些事情得。 在讲API签名认证之前&#xff0c;我们先模拟一个场景并且介绍…...

C#进阶-基于.NET Framework 4.x框架实现ASP.NET WebForms项目IP拦截器

在这篇文章中&#xff0c;我们将探讨如何在 ASP.NET WebForms 中实现IP拦截器&#xff0c;以便在 ASMX Web 服务方法 和 HTTP 请求 中根据IP地址进行访问控制。我们将使用自定义的 SoapExtension 和 IHttpModule 来实现这一功能&#xff0c;并根据常用的两种文本传输协议&#…...

前端(1)HTML

1、标签 创建1.html文件&#xff0c;浏览器输入E:/frontheima/1.html&#xff0c;可以访问页面 页面展示 在VSCODE安装IDEA的快捷键&#xff0c;比如ctld复制一行、ctrlx剪切 <p id"p1" title"标题1">Hello,world!</p> <p id"p2"…...

【北京迅为】《i.MX8MM嵌入式Linux开发指南》-第三篇 嵌入式Linux驱动开发篇-第五十三章 设备树下的platform驱动

i.MX8MM处理器采用了先进的14LPCFinFET工艺&#xff0c;提供更快的速度和更高的电源效率;四核Cortex-A53&#xff0c;单核Cortex-M4&#xff0c;多达五个内核 &#xff0c;主频高达1.8GHz&#xff0c;2G DDR4内存、8G EMMC存储。千兆工业级以太网、MIPI-DSI、USB HOST、WIFI/BT…...

Java正则表达式判断有无特殊字符

//^代表否定&#xff0c;匹配除了数字、字母、下划线的特殊字符。 private static final String SPECIAL_CHAR_PATTERN "[^a-zA-Z0-9_]"; Pattern pattern Pattern.compile(SPECIAL_CHAR_PATTERN); Matcher matcher pattern.matcher(userAccount); // 如果 find(…...

使用Java和Spring AMQP构建消息驱动应用

使用Java和Spring AMQP构建消息驱动应用 大家好&#xff0c;我是微赚淘客系统3.0的小编&#xff0c;是个冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01; 消息驱动应用程序在现代系统架构中扮演着重要角色&#xff0c;特别是在处理高并发和异步任务时。Spring AMQ…...

【NLP】提升文本生成多样性的实用方法

比如用T5模型,训练数据是inputText-outputText格式,预测时do_sample=False # 预测代码from transformers import TFAutoModelForSeq2SeqLM from transformers import AutoTokenizercheckpoint_local = "./path/" tokenizer = AutoTokenizer.from_pretrained(check…...

鸿蒙(HarmonyOS)下拉选择控件

一、操作环境 操作系统: Windows 11 专业版、IDE:DevEco Studio 3.1.1 Release、SDK:HarmonyOS 3.1.0&#xff08;API 9&#xff09; 二、效果图 三、代码 SelectPVComponent.ets Component export default struct SelectPVComponent {Link selection: SelectOption[]priva…...

Java类加载器实现机制详细笔记

1. 类加载器的基本概念 类加载器&#xff08;ClassLoader&#xff09;&#xff1a;在Java中&#xff0c;类加载器负责将Java类动态加载到JVM中。它是实现动态类加载机制的核心组件&#xff0c;对于开发复杂应用程序&#xff08;如插件系统、模块化设计等&#xff09;至关重要。…...

Git之repo sync -l与repo forall -c git checkout用法区别(四十九)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

AxureRP-Pro-Beta-Setup_114413.exe (6.0.0.2887)

Name&#xff1a;3ddown Serial&#xff1a;FiCGEezgdGoYILo8U/2MFyCWj0jZoJc/sziRRj2/ENvtEq7w1RH97k5MWctqVHA 注册用户名&#xff1a;Axure 序列号&#xff1a;8t3Yk/zu4cX601/seX6wBZgYRVj/lkC2PICCdO4sFKCCLx8mcCnccoylVb40lP...