【OJ】单链表刷题
力扣刷题
- 1. 反转链表(206)
- 1.1 题目描述
- 1.2 题目分析
- 1.2.1 头插法
- 1.2.2 箭头反转
- 1.3 题目代码
- 1.3.1 头插入
- 1.3.2 箭头反转
- 2.合并两个有序链表(21)
- 2.1 题目描述
- 2.2 题目分析
- 2.3 题目代码
1. 反转链表(206)
1.1 题目描述


1.2 题目分析
1.2.1 头插法
要将原来的链表进行反转,很容易想到,将原来的节点取下来,然后一个一个进行头插到新链表中struct ListNode* newhead=NULL。
原链表中,如果cur不为空,那么cur->next=newhead,再将newhead置为新链表的头节点。
为了方便记录原链表节点的位置,在原链表上定义一个struct ListNode* next=cur->next。

如果cur为空,这里就需要一个新的链表,所以最后不要忘记返回新链表的头节点。

1.2.2 箭头反转
还有一种方法就是将这些节点的箭头反向,也就是将后一个节点的next等于前一个节点。

反转之后就是这样:

也就是说:先定义两个指针,先将n1置为空,然后n2指向头节点,再将n2->next=n1。然后继续往后走,需要记录n2后一个节点位置,再定义一个n3=head->next,只要链表不为空,就让 n2->next=n1;n1=n2;n2=n3。
但是在最后一步n3可能为空,所以得加一个判断,为空就不往后执行了。
最值得注意的一点是,如果原链表为空,那么后面都不执行,所以开始得加一个判断
if(head==NULL){return NULL;}
1.3 题目代码
1.3.1 头插入
struct ListNode* reverseList(struct ListNode* head){struct ListNode* cur=head;struct ListNode* newhead=NULL;while(cur){struct ListNode* next=cur->next;cur->next=newhead;newhead=cur;cur=next;}return newhead;
}
1.3.2 箭头反转
struct ListNode* reverseList(struct ListNode* head){if(head==NULL){return NULL;}struct ListNode* n1,*n2,*n3;n1=NULL;n2=head;n3=head->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3){n3=n3->next;}}return n1;
}
2.合并两个有序链表(21)
2.1 题目描述


2.2 题目分析
题目要求是按照升序返回合并的原来排好序的两个链表,这里就可以用尾插,比较两个链表节点的val,对比一下,取小的进行尾插。

这里肯定要事先判断一下这两个链表是不是为空:如果链表1为空,就直接返回链表2。同样,链表2为空,就返回链表1。
if(list1==NULL){return list2;}if(list2==NULL){return list1;}
在已有的链表上面经行插入比较繁琐,就直接用一个新的,最后返回排好链表的头节点就行。
只有两个链表都不为空时,再考虑是链表1节点的val与链表2的val:如果 list1->val< list2->val,还是得判断一下这个新链表里面有没有节点:没有就直接让head=tail=list1,有就实现尾插。
if(tail==NULL){head=tail=list1;}else{tail->next=list1;tail=tail->next;}
然后链表1继续往后走。
但是如果 list1->val< list2->val是错误的,那么链表2也是同样的:
if (tail == NULL){head = tail = list2;}else{tail->next = list2;tail = tail->next;}list2 = list2->next;
当一个链表已经排好了,如果剩下的是链表1,就直接插入
if(list1){tail->next=list1;}
如果剩下的是链表2,就直接插入:
if(list2){tail->next=list2;}
最后别忘记返回头节点。
2.3 题目代码
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){if(list1==NULL){return list2;}if(list2==NULL){return list1;}struct ListNode* head=NULL;struct ListNode* tail=NULL;while(list1&&list2){if(list1->val<list2->val){if(tail==NULL){head=tail=list1;}else{tail->next=list1;tail=tail->next;}list1=list1->next;}else{if(tail==NULL){head=tail=list2;}else{tail->next=list2;tail=tail->next;}list2=list2->next;}}if(list1){tail->next=list1;}if(list2){tail->next=list2;}return head;}
相关文章:
【OJ】单链表刷题
力扣刷题 1. 反转链表(206)1.1 题目描述1.2 题目分析1.2.1 头插法1.2.2 箭头反转 1.3 题目代码1.3.1 头插入1.3.2 箭头反转 2.合并两个有序链表(21)2.1 题目描述2.2 题目分析2.3 题目代码 1. 反转链表(206)…...
【UML建模】部署图(Deployment Diagram)
1.概述 部署图是一种结构图,用于描述软件系统在不同计算机硬件或设备上的部署和配置情况,以图形化的方式展示系统中组件、节点和连接之间的物理部署关系。 通过部署图,可以清晰地了解系统的物理结构和部署方式,包括系统组件和节…...
三、计算机理论-关系数据库-数据模型与数据视图;关系代数、关系演算及关系模型
数据模型 具体事物-抽象化-->概念模型-数据化-->数据模型 概念模型也称信息模型,在数据库设计阶段,由设计者按照用户的观点对数据和信息建模,实现对现实世界的概念抽象; 数据模型主要包括网状模型、层次模型、关系模型、面向…...
解读 $mash 通证 “Fair Launch” 规则(Staking 玩法解读篇)
Solmash 是 Solana 生态中由社区主导的铭文资产 LaunchPad 平台,该平台旨在为 Solana 原生铭文项目,以及通过其合作伙伴 SoBit 跨链桥桥接到 Solana 的 Bitcoin 生态铭文项目提供更广泛的启动机会。...
【C语言】关于C11的一些新特性
相比于VC 6.0使用的ANSI C标准,VS2022使用的C11标准与上一代有很多不同,相比之前的 C 标准(如 C89/C90 和 C99),引入了一些新的功能、特性和改进。以下是 C11 标准相对于之前版本的一些主要变化和新增内容:…...
牛的速记(c++题解)
题目描述 奶牛们误解了速记的含义。他们是这样理解的: 给出一个少于255个字母的小写字母串。 找到一个出现次数最多的字母,将该字母从字母串中统统删去,如果出现次数最多的字母不止一个,就删去在字母表中靠前的一个,即…...
使用ffmpeg+flv.js + websokect播放rtsp格式视频流
对于rtsp的视频流网上有很多种的解决方案,但是大的趋势还是利用ffmpeg的工具进行rtsp的视频解析进行一个推流,我最终选择bilibili开源的flv.js,代码十分的简单全部都在底层封装好了。实现的方式也比较容易理解,ffmpeg进行rtsp的视…...
OAI openair3代码结构整理
openair3代码框架结构 OAI(OpenAirInterface)是一个开源的5G网络软件平台,用于研究和开发5G网络技术。OpenAir3是OAI项目中的一个子项目,专注于5G核心网络的功能实现。 一、OpenAir3的代码主要包括以下几个部分: NAS…...
Kubernets(K8S)启动和运行 01-01 Kubernetes简介
Kubernets(K8S)启动和运行 01-01 Kubernetes简介 Kubernetes is an open source orchestrator for deploying containerized applications. It was originally developed by Google, inspired by a decade of experience deploying scalable, reliable systems in containers …...
PHP特性知识点扫盲 - 下篇
概述 在实际的生产环境中遇到了实际需要解决的问题,需要把服务部署的方式梳理出来,在同一个服务器中部署多个PHP环境,架构图如下: 架构方案 在工作实践中遇到的很多问题的普遍性都是相通的,公司运行的可新项目都是版…...
HarmonyOS应用开发之DevEco Studio安装与初次使用
1、DevEco Studio介绍 DevEco Studio是基于IntelliJ IDEA Community开源版本打造,面向华为终端全场景多设备的一站式集成开发环境(IDE),为开发者提供工程模板创建、开发、编译、调试、发布等E2E的HarmonyOS应用/服务的开发工具。…...
记录第一次在GitHub上面提交Issue
第一次在GitHub上面提交Issue,记录一下。 对着源码调了好久才发现,问题并不在程序而在模型(虽然只是一个很小的问题,但是能够解决问题,并且做出了自己的一点小小贡献,还是很开心。嘻嘻,发博客记…...
【数据库设计和SQL基础语法】--用户权限管理--数据备份和恢复策略
一、引言 数据备份和恢复是数据库管理中至关重要的任务,对于确保数据安全性和业务连续性具有重大的意义。以下是一些关键的重要性方面: 防止数据丢失: 数据备份是防止因硬件故障、人为错误、恶意攻击或其他意外事件导致数据丢失的主要手段。…...
java数据结构与算法刷题-----LeetCode70. 爬楼梯
java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846 很多人觉得动态规划很难,但它就是固定套路而已。其实动态规划只…...
【Unity入门】UGUI之Slider(滑动条)
目录 一、什么是Slider?二、Slider属性与功能 一、什么是Slider? Slider控件允许用户可以通过鼠标来在预先确定的范围调节数值 我们可以在Hierarchy视图右键 -> UI ->Slider来创建滑动条 通过上图可以发现Unity内置的Slider主要有3部分&#x…...
MySQL中UNION和UNION ALL的区别有哪些?
在MySQL中如何想要对两个结果集进行合并操作,可以使用UNION和UNION ALL,如果只是想要去除掉重复的记录,属于UNION ALL 即可,但是如何想要除掉没有重复行数据,就要使用Union。本文详细向大家介绍MySQL中UNION和UNION AL…...
Android kotlin build.gradle.kts配置
1. 添加 maven 仓库 1. 1. settings配置 1. 1.1. settings.gradle repositories {maven {url https://maven.aliyun.com/repository/public/}mavenCentral() }1. 1.2. settings.gradle.kts repositories {maven {setUrl("https://maven.aliyun.com/repository/public/…...
css、js、vue常考部分面试题
css css盒子水平垂直居中方法 方法一:定位 .child{height: 100px;position: absolute;//父元素相对定位top:50%;left:50%;transform: translate(-50%,-50%); } 方法二:定位 .child{width: 100px;height: 100px;position: absolute;top:50%;left:50%…...
OpenAI ChatGPT-4开发笔记2024-03:Chat之Function Calling/Function/Tool/Tool_Choice
Updates on Function Calling were a major highlight at OpenAI DevDay. In another world,原来的function call都不再正常工作了,必须全部重写。 function和function call全部由tool和tool_choice取代。2023年11月之前关于function call的代码都准备翘翘。 干嘛…...
二叉搜索树与双向链表
解题思路一: /** public class TreeNode {int val 0;TreeNode left null;TreeNode right null;public TreeNode(int val) {this.val val;} } */ // 一定要用自己的理解真正弄出来才行,否则没有用! // 再次提醒,计算机这种工科…...
Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...
Chrome 浏览器前端与客户端双向通信实战
Chrome 前端(即页面 JS / Web UI)与客户端(C 后端)的交互机制,是 Chromium 架构中非常核心的一环。下面我将按常见场景,从通道、流程、技术栈几个角度做一套完整的分析,特别适合你这种在分析和改…...
xmind转换为markdown
文章目录 解锁思维导图新姿势:将XMind转为结构化Markdown 一、认识Xmind结构二、核心转换流程详解1.解压XMind文件(ZIP处理)2.解析JSON数据结构3:递归转换树形结构4:Markdown层级生成逻辑 三、完整代码 解锁思维导图新…...
CSS3相关知识点
CSS3相关知识点 CSS3私有前缀私有前缀私有前缀存在的意义常见浏览器的私有前缀 CSS3基本语法CSS3 新增长度单位CSS3 新增颜色设置方式CSS3 新增选择器CSS3 新增盒模型相关属性box-sizing 怪异盒模型resize调整盒子大小box-shadow 盒子阴影opacity 不透明度 CSS3 新增背景属性ba…...
高抗扰度汽车光耦合器的特性
晶台光电推出的125℃光耦合器系列产品(包括KL357NU、KL3H7U和KL817U),专为高温环境下的汽车应用设计,具备以下核心优势和技术特点: 一、技术特性分析 高温稳定性 采用先进的LED技术和优化的IC设计,确保在…...
更新 Docker 容器中的某一个文件
🔄 如何更新 Docker 容器中的某一个文件 以下是几种在 Docker 中更新单个文件的常用方法,适用于不同场景。 ✅ 方法一:使用 docker cp 拷贝文件到容器中(最简单) 🧰 命令格式: docker cp <…...
