【基础算法】单链表的OJ练习(1) # 反转链表 # 合并两个有序链表 #
文章目录
- 前言
- 反转链表
- 合并两个有序链表
- 写在最后
前言
-
上一章讲解了单链表 -> 传送门 <- ,后面几章就对单链表进行一些简单的题目练习,目的是为了更好的理解单链表的实现以及加深对某些函数接口的熟练度。
-
本章带来了两个题目。一是反转链表,二是合并两个有序链表,整体难度不大,但要理清解题思路。
反转链表
题目链接 -> 传送门 <-
- 该题目的意思是将一个单链表反转过来,单链表的尾节点变成新的头节点,头节点变成新的尾节点:

-
题目描述是,给你一个单链表的头节点
head,请你反转链表,并返回反转后的链表。 -
返回反转后的链表也就是返回反转后的链表的头节点。
思路一:
- 创建一个新的链表,取原链表的元素依次头插即可,最后返回这个新的链表的头节点。

思路二:
-
直接修改原链表,返回原链表的尾节点(反转后的头节点)即可。
-
定义三个指针遍历原链表,三个指针 (prev,cur,tail)
prev开始指向NULL,cur指向头节点,tail指向cur的下一个节点(为了找到下一个)。具体操作就是cur->next = prev(将指针改变指向),然后prev = cur,cur = tail,tail = cur->next(该语句在循环的开头)。这样又是三个指针指向不同的节点,然后再将cur的指针指向前一个prev,整个过程其实就是一个循环。 -
循环的条件是
cur不为NULL就继续,当cur为空,也就是最后一步cur = tail,此时cur,tail都为空,而prev刚好指向原链表的最后一个节点,所以最后返回prev就可以了。

这里采用思路二进行代码实现:
struct ListNode* reverseList(struct ListNode* head){struct ListNode* cur = head;struct ListNode* prev = NULL;while (cur){struct ListNode* tail = cur->next;cur->next = prev;prev = cur;cur = tail;}return prev;
}
合并两个有序链表
题目链接 -> 传送门 <-。
- 题目描述:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

-
该题与归并排序的排序思路差不多。本题需要创建一个新链表。之后采用双指针分别遍历上下两个链表,那个节点的数据较小,就在新的链表中尾插该节点,然后指向该节点的指针向后移动一位。整体来说就是一个循环,循环结束的条件就是两个指针都指向了
NULL或者其中一个指针指向了NULL。 -
注意,我们这里的新链表是不带哨兵位的,当然带哨兵位可能更加方便,最后需要返回哨兵位的下一个节点的指针。
-
如果循环结束后,有一个指针没有指向
NULL,那么在后面还需要将剩余的节点依次尾插,直到两个指针都为NULL合并成功。

代码实现:
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode* l1 = list1, * l2 = list2; // 两个指针分别指向两个链表的头struct ListNode* head = NULL, * cur = NULL; // 新链表的头和进行操作的指针curwhile (l1 && l2) // 有一个指向空就结束{if (l1->val < l2->val) // 比较数据值{if (!head) head = cur = l1; // 这个if是如果新链表为空,就将该节点作为头节点else cur->next = l1, cur = cur->next;l1 = l1->next;}else{if (!head) head = cur = l2;else cur->next = l2, cur = cur->next;l2 = l2->next;}}// 如果l1不为空说明l1还有节点没有尾插完,需继续尾插while (l1){if (!head) head = cur = l1;else cur->next = l1, cur = cur->next;l1 = l1->next;}// 如果l2不为空说明l2还有节点没有尾插完,需继续尾插while (l2){if (!head) head = cur = l2;else cur->next = l2, cur = cur->next;l2 = l2->next;}// 最后返回新链表的头节点return head;
}
写在最后
对于单链表的题目练习,最重要的是思路,我们在数据结构阶段要养成画图的习惯,因为它能帮助我们更好的理解。后续还会有单链表相关的题目练习。
感谢阅读本小白的博客,错误的地方请严厉指出噢!
相关文章:
【基础算法】单链表的OJ练习(1) # 反转链表 # 合并两个有序链表 #
文章目录前言反转链表合并两个有序链表写在最后前言 上一章讲解了单链表 -> 传送门 <- ,后面几章就对单链表进行一些简单的题目练习,目的是为了更好的理解单链表的实现以及加深对某些函数接口的熟练度。 本章带来了两个题目。一是反转链表&#x…...
离散数学笔记(1)命题逻辑
文章目录1.命题符号化及联结词基本概念本节题型2.命题公式及分类基本概念本节题型1.命题符号化及联结词 基本概念 命题的定义:能够判断真假的陈述句称为命题。 备注:感叹句、疑问句、祈使句和类似于xy>5之类真值不唯一的句子都不是命题。 真值的真假…...
IDEA Android 网格布局(GridLayout)示例(计算器界面布局)
网格布局(GridLayout) 示例程序效果(实现类似vivo手机自带计算器UI) 真机和模拟器运行效果: 简述: GridLayout(网格布局)和TableLayout(表格布局)有类似的地方,通俗来讲可以理解为…...
【蓝桥杯嵌入式】拓展板之数码管显示
文章目录硬件电路连接方式函数实现文章福利硬件电路 通过上述原理图,可知拓展板上的数码管是一个共阴数码管,也就是说某段数码管接上高电平时,就会点亮。 上述原理图还给出一个提示,即:三个数码管分别与三个74HC59…...
Web Spider案例 网洛克 第三题 AAEncode加密 练习(七)
声明 此次案例只为学习交流使用,抓包内容、敏感网址、数据接口均已做脱敏处理,切勿用于其他非法用途; 文章目录声明一、资源推荐二、逆向目标三、抓包分析 & 下断分析逆向3.1 抓包分析3.2 下断分析逆向拿到混淆JS代码3.3 AAEncode解决方…...
【javaScript面试题】2023前端最新版javaScript模块,高频24问
🥳博 主:初映CY的前说(前端领域) 🌞个人信条:想要变成得到,中间还有做到! 🤘本文核心:博主收集的关于javaScript的面试题 目录 一、2023javaScript面试题精选 1.js的数据类型…...
Hadoop集群启动从节点没有DataNode
一、问题背景 之前启动hadoop集群的时候都没有问题,今天启动hadoop集群的时候,从节点的DataNode没有启动起来。 二、解决思路 遇见节点起不来的情况,可以去看看当前节点的日志文件 我进入当前从节点的hadoop安装目录的Logs文件下去查看日…...
FIFO IP Core
FIFO IP Core 先进先出的缓存器常常被用于数据的缓存,或者高速异步数据交互(跨时钟信号传递)和RAM和ROM的区别是没有地址线,无法指定地址 写时钟(Write Clock Domain),读时钟写复位(wr_rst),读…...
从FPGA说起的深度学习(四)
这是新的系列教程,在本教程中,我们将介绍使用 FPGA 实现深度学习的技术,深度学习是近年来人工智能领域的热门话题。在本教程中,旨在加深对深度学习和 FPGA 的理解。用 C/C 编写深度学习推理代码高级综合 (HLS) 将 C/C 代码转换为硬…...
pytorch入门7--自动求导和神经网络
深度学习网上自学学了10多天了,看了很多大神的课总是很快被劝退。终于,遇到了一位对小白友好的刘二大人,先附上链接,需要者自取:https://b23.tv/RHlDxbc。 下面是课程笔记。 一、自动求导 举例说明自动求导。 torch中的…...
QT 之wayland 事件处理分析基于qt5wayland5.14.2
1. Qt wayland 初始化 接收鼠标/案件,触摸屏等事件事件 QWaylandNativeInterface : public QPlatformNativeInterface 在QWaylandNativeInterface 继承qpa 接口类QPlatformNativeInterface; 1.1 初始化鼠标: void *QWaylandNativeInterface::nativeR…...
【this 和 super 的区别】
在 Java 中,this 和 super 都是关键字,表示当前对象和父类对象。 this 关键字可以用于以下几种情况: 引用当前对象的成员变量,方法和构造方法,用于区分局部变量和成员变量重名的情况; 调用当前类的另外一…...
K8s:Monokle Desktop 一个集Yaml资源编写、项目管理、集群管理的 K8s IDE
写在前面 Monokle Desktop 是 kubeshop 推出的一个开源的 K8s IDE相关项目还有 Monokle CLI 和 Monokle Cloud相比其他的工具,Monokle Desktop 功能较全面,涉及 k8s 管理的整个生命周期博文内容:Monokle Desktop 下载安装,项目管理…...
自动化测试实战篇(8),jmeter并发测试登录接口,模拟从100到1000个用户同时登录测试服务器压力
首先进行使用jmeter进行并发测试之前就需要搞清楚线程和进程的区别还需要理解什么是并发、高并发、并行。还需要理解高并发中的以及老生常谈的,TCP三次握手协议和TCP四次握手协议**TCP三次握手协议指:****TCP四次挥手协议:**进入Jmeter&#…...
ATTCK v12版本战术实战研究—持久化(二)
一、前言前几期文章中,我们介绍了ATT&CK中侦察、资源开发、初始访问、执行战术、持久化战术的知识。那么从前文中介绍的相关持久化子技术来开展测试,进行更深一步的分析。本文主要内容是介绍攻击者在运用持久化子技术时,在相关的资产服务…...
python函数式编程
1 callable内建函数判断一个名字是否为一个可调用函数 >>> import math >>> x 1 >>> y math.sqrt >>> callable(x) False >>> callable(y) True 2 记录函数(文档字符串) >>> def square(x): …...
3.linux下安装mysql
1.安装前的环境准备 查看是否安装过mysql 首先检测Linux操作系统中是否安装了MySQL: # rpm -qa | grep -i mysql 卸载安装包 如果有信息出现,则进行删除,命令如下: # rpm -e --nodeps 包名 删除老版本mysql的开发头文件和…...
17、MySQL分库分表,原理实战
MySQL分库分表,原理实战 1.MyCAT分布式架构入门及双主架构1.1 主从架构1.2 MyCAT安装1.3 启动和连接1.4 配置文件介绍2.MyCAT读写分离架构2.1 架构说明2.2 创建用户2.3 schema.xml2.4 连接说明2.5 读写测试2.6 当前是单节点3.MyCAT高可用读写分离架构3.1 架构说明3.3 schema.xm…...
【C++的OpenCV】第九课-OpenCV图像常用操作(六):图像形态学-阈值的概念、功能及操作(threshold()函数))
目录一、阈值(thresh)的概念二、阈值在图形学中的用途三、阈值的作用和操作3.1 在OpenCV中可以进行的阈值操作3.2 操作实例3.2.1 threshold()函数介绍3.2.2 实例3.2.3 结果上节课的内容(作者还是鼓励各位同学按照顺序进行学习哦)&…...
[Java代码审计]—MCMS
环境搭建 MCMS 5.2.4:https://gitee.com/mingSoft/MCMS/tree/5.2.4/利用 idea 打开项目 创建数据库 mcms,导入 doc/mcms-5.2.8.sql 修改 src/main/resources/application-dev.yml 中关于数据库设置参数 启动项目登录后台 http://localhost:8080/ms/l…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】
大家好,我是java1234_小锋老师,看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】,分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...
什么是VR全景技术
VR全景技术,全称为虚拟现实全景技术,是通过计算机图像模拟生成三维空间中的虚拟世界,使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验,结合图文、3D、音视频等多媒体元素…...
