【数据结构】链表OJ(二)

Yan-英杰的博客
悟已往之不谏 知来者之可追
目录
一、反转链表
二、合并两个有序链表
三、链表分割
四、链表的回文结构
一、反转链表

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
![]()
输入:head = [1,2]
输出:[2,1]
示例 3:
输入:head = []
输出:[]
提示:
- 链表中节点的数目范围是
[0, 5000]-5000 <= Node.val <= 5000
方法一:
代码解析:
struct ListNode* reverseList(struct ListNode* head){if(head == NULL){return NULL;}struct 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;
}
画图解析:

注:该题使用到了三指针
方法二:
代码解析:
struct ListNode* reverseList(struct ListNode* head){struct ListNode* cur = head,*newhead = NULL;while(cur){struct ListNode* next = cur->next;//头插cur->next = newhead;newhead = cur;cur = next;}return newhead;
}
画图解析:
此方法采用头插方式
二、合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
示例 2:
输入:l1 = [], l2 = []
输出:[]
示例 3:
输入:l1 = [], l2 = [0]
输出:[0]
提示:
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
代码解析:
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}struct ListNode* cur1 = list1,*cur2 = list2;struct ListNode* head = NULL,*tail = NULL;while(cur1 && cur2){if(cur1->val < cur2->val){if(head == NULL){head = tail = cur1;}else{tail->next = cur1;tail = tail->next;}cur1 = cur1->next;}else{if(head == NULL){head = tail = cur2;}else{tail->next = cur2;tail = tail->next;}cur2 = cur2->next;}}if(cur1){tail->next = cur1;}if(cur2){tail->next = cur2;}return head;
}
画图解析:

三、链表分割
描述
现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。
思路:
小于尾插到一个链表,大于等于尾插到另一个链表,再将两个链表链接起来
代码解析:
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code herestruct ListNode* gGurad,*gTail,*lGuard,*lTail;gGurad = gTail = (struct ListNode*)malloc(sizeof(struct ListNode));lGuard = lTail = (struct ListNode*)malloc(sizeof(struct ListNode));gTail->next = lTail->next = NULL;struct ListNode* cur = pHead;while(cur){if(cur->val < x){lTail->next = cur;lTail = lTail->next;}else{gTail->next = cur;gTail = gTail->next;}cur= cur->next;}lTail->next = gGurad->next;gTail->next =NULL;pHead = lGuard->next;free(gGurad);free(lGuard);return pHead;}
};
画图解析:

此题我们需要用到哨兵位的头节点
四、链表的回文结构
描述
对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。
给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。
测试样例:
1->2->2->1
返回:true
代码解析:
//查找中间节点
struct ListNode* Mid(struct ListNode* Head) {struct ListNode* slow = Head;struct ListNode* fast = Head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}return slow;
}//链表逆置
struct ListNode* reverse(struct ListNode* Head)
{struct ListNode* cur = Head;struct ListNode* phead = NULL;while(cur){struct ListNode* next = cur->next;cur->next = phead;phead = cur;cur = next;}return phead;
}class PalindromeList {public:bool chkPalindrome(ListNode* A) {struct ListNode* MidList = Mid(A);struct ListNode* ReList = reverse(MidList);struct ListNode* pphead = A;struct ListNode* ppheadR = ReList;while(pphead && ppheadR){if(pphead->val != ppheadR->val){return false;}else{pphead = pphead->next;ppheadR = ppheadR->next;}}return true;}
};
画图解析:

相关文章:
【数据结构】链表OJ(二)
Yan-英杰的博客 悟已往之不谏 知来者之可追 目录 一、反转链表 二、合并两个有序链表 三、链表分割 四、链表的回文结构 一、反转链表 输入:head [1,2,3,4,5] 输出:[5,4,3,2,1] 输入:head [1,2] 输出:[2,1] 示例 3…...
Linux系统搭建FTP服务器
安装vsftpdyum -y install vsftpd添加FTP用户方式1、添加只允许通过ftp访问的用户useradd -d /home/ftp ftp_user #-d指定用户登录时的启始目录方式2、允许用户登录操作系统usermod -d /home/ftp -s /bin/bash ftp_user #-s指定用户登入后所使用的shell设置用户登录密码passwd …...
MySQL数据同步到 Redis 缓存的几种方法
1 Mysql查完数据,再同步写入到Redis中缺点1:会对接口造成延迟,因为同步写入redis本身就有延迟,并且还要做重试,如果redis写入失败,还需要重试,那就更费时间了。缺点2:不解耦…...
2023年网络安全比赛--CMS网站渗透中职组(超详细)
一、竞赛时间 180分钟 共计3小时 二、竞赛阶段 1.使用渗透机对服务器信息收集,并将服务器中网站服务端口号作为flag提交; 2.使用渗透机对服务器信息收集,将网站的名称作为flag提交; 3.使用渗透机对服务器渗透,将可渗透页面的名称作为flag提交; 4.使用渗透机对服务器渗透,…...
【蓝桥杯集训·每日一题】AcWing 4309. 消灭老鼠
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴最大公约数一、题目 1、原题链接 4309. 消灭老鼠 2、题目描述 约翰的农场可以看作一个二维平面。 农场中有 n 个老鼠,在毁坏着农田。 第 i 个老鼠的位置坐标为…...
FPGA实现CSI-2 解码MIPI视频 2line 720P分辨率 OV5647采集 提供工程源码和技术支持
目录1、前言2、Xilinx官方主推的MIPI解码方案3、纯Vhdl方案解码MIPI4、vivado工程介绍5、上板调试验证6、福利:工程代码的获取1、前言 FPGA图像采集领域目前协议最复杂、技术难度最高的应该就是MIPI协议了,MIPI解码难度之高,令无数英雄竞折腰…...
JS面试题收集(持续更新好中...)
1.JavaScript 中的垃圾回收机制 定义:指一块被分配的内存既不能使用,又不能回收,直到浏览器进程结束。 JavaScript在创建对象时会为它们分配内存,不再使用时会自动释放内存,这个过程称为垃圾收集。 四种常见的内存泄…...
2023携程面试题
Java I/O 面试前需要准备: 1. Java 八股文:了解常考的题型和回答思路; 2. 算法:刷 100-200 道题,记住刷题最重要的是要理解其思想,不要死记硬背,碰上原题很难,但 大多数的解题思…...
CANoe中使用CAPL函数接口调用Vflash文件
🍅 我是蚂蚁小兵,专注于车载诊断领域,尤其擅长于对CANoe工具的使用🍅 寻找组织 ,答疑解惑,摸鱼聊天,博客源码,点击加入👉【相亲相爱一家人】🍅 玩转CANoe&…...
三天吃透计算机网络面试八股文
本文已经收录到Github仓库,该仓库包含计算机基础、Java基础、多线程、JVM、数据库、Redis、Spring、Mybatis、SpringMVC、SpringBoot、分布式、微服务、设计模式、架构、校招社招分享等核心知识点,欢迎star~ Github地址:https://github.com/…...
shp数据添加wkt字段并导出成csv,leaflet绘制使用
准备的东西:软件2跟软件3具体怎么有这些软件需要自行百度postgresql postgis相关 1.shp数据 2.软件2 3.软件3 1.数据导入 首先你得有软件2的数据库,即postgresql数据库,然后通过postgis的插件进行连接并导入数据, 导入数据…...
Java——二叉树的最近公共祖先及二叉搜索树介绍
目录 二叉树的最近公共祖先 题目 思路一:如果给定的是一颗二叉搜索树, 思路二:假设是孩子双亲表示法 二叉搜索树 定义Node类 查找 删除 插入 二叉树的最近公共祖先 题目 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百…...
Stable Diffusion加chilloutmixni真人图片生成模型,AI绘图杀疯了
上期图文教程,我们分享过AI绘图大模型Stable Diffusion以及中文版本文心AI绘画大模型的基础知识以及代码实现,截至到目前为止。Stable Diffusion模型已经更新到了V2.1版本,其文生图大模型也越来越火,其在2022年底,由AI绘制的图片被荣为国际大奖,让大家对AI绘画大模型也越…...
Matplotlib 绘图实用大全
本文只介绍最简单基本的画图方法 预设 要想画出来的图有些逼格,首先应该进行如下设置 plt.rcParams[font.sans-serif][SimHei] #画图时显示中文字体 plt.rcParams[axes.unicode_minus] False #防止因修改成中文字符,导致某些 unicode 字符不能…...
MyBatis源码用了哪些设计模式?
MyBatis源码用了哪些设计模式?前言一、创建型模式工厂模式单例模式建造者模式二、结构型模式适配器模式代理模式组合模式装饰器模式三、行为型模式模板模式策略模式迭代器模式总结前言 在 MyBatis 的两万多行的框架源码中,使用了大量的设计模式对工程架…...
【16.整数转罗马数字】
罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例…...
前端小技巧
1.html 1.1 网站自动刷新 应用场景: 网页定期自动刷新(现在基本淘汰了,采用ajax);自动跳转到指定页面,这个自动跳转的好处就是不需要JS调用,属于纯html网页自动跳转 v7-网站自动刷新 你可以…...
Servlet2.0
文章目录更方便的部署方式安装插件使用插件验证程序常见访问出错的解决方案404错误405错误500错误空白页面无法访问此网站在文章 TomcatServlet初识中,我们通过七个大的步骤才可以完成一个简单的Servlet程序,这个过程无疑是非常繁琐的,那么我…...
【c++】继承
目录 一、继承的表现 子类对父类成员的访问权限 二、父类与子类之间的相互赋值 三、继承的作用域 如果是父类和子类构成隐藏呢? 四、子类的成员函数怎么写 1.default构造函数 2.析构函数 所以析构函数不需要我们显式调用。 五、继承与友元函数 六、继承与静…...
minio安装配置和使用(二)客户端安装
安装minio客户端mcli 命令如下: dnf install https://dl.minio.org.cn/client/mc/release/linux-amd64/mcli-20230128202938.0.0.x86_64.rpm 安装完成,在/usr/local/bin/下新增了mcli命令 mcli是对minio进行管理的命令。功能丰富, 基本格式…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
