力扣24.两两交换链表中的节点
文章目录
- 力扣24.两两交换链表中的节点
- 题目描述
- 方法1:非递归
- 方法2:递归
力扣24.两两交换链表中的节点
题目描述
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例 1:
输入:head = [1,2,3,4]
输出:[2,1,4,3]
示例 2:
输入:head = []
输出:[]
示例 3:
输入:head = [1]
输出:[1]
提示:
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
方法1:非递归
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* swapPairs(struct ListNode* head){if(head==NULL||head->next==NULL) return head;//如果是空链表或者只有一个元素则直接返回struct ListNode *p=head,*t,*pre=NULL;if(p->next!=NULL) head=p->next;//直接指定最终的返回位置,即应当是原始第二个节点(不为空)while(p!=NULL){t=p->next->next;//记录后继节点的下一个位置if(pre!=NULL) pre->next=p->next;//将前驱节点接到后续节点上,防止断链pre=p;//将本节点标记为下一次的前驱节点p->next->next=p;//交换相邻节点,即让相邻节点的后继指针指向当前节点p->next=t;//当前节点的后继指针指向原后继节点的后继p=t;//更新当前节点的位置,准备进行下一次交换if(p!=NULL&&p->next==NULL) return head;//如果更新后只剩下单独一个节点了则不用再交换了,立即返回结果}return head;
}
方法2:递归
从第一个节点开始,要通过递归的方式寻找交换之后该节点的下一个节点,规律是:
- 第1个节点的下一个节点是下一个节点的下一个节点,即第3个节点
- 第2个节点的下一个节点是第1个节点
- 以此类推
递归函数中其中一个重大的作用就是为它的上一级调用函数返回需要的节点作为上一级递归中的下一个节点,我们暂存这个节点,在需要结束时返回给上一级函数。
struct ListNode *p=head->next;
同时我们通过调用下一级递归函数的方式来期望获得当前节点交换后连接的下一个节点,注意一次调用的步长为2,即隔一个节点进行下一次调用:
head->next=swapPairs(head->next->next);
并且根据规律,本节点的前驱节点也应改成本节点的原后继节点,即上面暂存的节点P
p->next=head;
最终递归函数完整应写成如下形式:
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* swapPairs(struct ListNode* head){if(head==NULL||head->next==NULL) return head;//如果节点为空或者只剩单一节点终止递归,返回struct ListNode *p=head->next;//记录当前节点的下一个节点head->next=swapPairs(head->next->next);p->next=head;return p;
}
相关文章:
力扣24.两两交换链表中的节点
文章目录力扣24.两两交换链表中的节点题目描述方法1:非递归方法2:递归力扣24.两两交换链表中的节点 题目描述 给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题&…...
AtCoder Regular Contest 137 题解(A~C)
A-Coprime Pair 思路 我们知道两个质数之间并不会相隔太远,于是我们直接用暴力就可以通过这题。 先从大到小枚举答案,并且枚举所有可能的起点,当枚举到的两个值满足条件输出并结束程序即可。 代码 #include <bits/stdc.h> using n…...
【C语言】预处理指令
C语言预处理指令一、什么是预处理指令二、预处理指令特点三、文件包含四、C标准库<stdio.h>一、什么是预处理指令 C语言的源文件(.c文件)需要经过编译生成可执行程序,编译操作会将源文件转换成目标文件,对于 VC、VS&#x…...
Java基础之多线程JUC全面学习笔记
目录初识多线程多线程的实现方式常见的成员方法线程安全的问题死锁生产者和消费者线程池自定义线程池初识多线程 什么是多线程? 线程 线程是操作系统能够进行运算调度的最小单位。线程被包含在进程之中,是进程中的实际运作单位。 简单理解:应用软件中互相独立&…...
13.CSS文本样式
文本样式 h1 {color: blue; }● 回顾上一节的内容,我们让h1标题的文字变成了蓝色,注意如果html中有多个h1标签,那我们这种写法所有的h1标签都会变成蓝色,除了颜色,本节我们将学习更多的CSS属性 文字大小font-size h…...
西恩科技更新招股书:IPO前大手笔分红“套现”, 赵志安为实控人
2月14日,上海西恩科技股份有限公司(下称“西恩科技”)更新了招股书(申报稿)。据贝多财经了解,西恩科技于2022年8月12日递交上市申请材料,准备在创业板上市,此次是西恩科技第二次更新…...
【CentOS】有关时间的设置
目录环境信息date语法信息查看时间设置时间设置日期tzselecttimedatectl语法显示当前及所有时区修改时区hwclock语法读取硬件时钟使用硬件时钟设置系统时间使用系统时间设置硬件时钟如何理解硬件时钟和系统时钟环境信息 CentOS 7 date 语法信息 date --help用法:…...
OpenCV制作Mask图像掩码
一、掩膜(mask) 在有些图像处理的函数中有的参数里面会有mask参数,即此函数支持掩膜操作,首先何为掩膜以及有什么用,如下: 数字图像处理中的掩膜的概念是借鉴于PCB制版的过程,在半导体制造中&am…...
C++STL剖析(九)—— unordered_map和unordered_multimap的概念和使用
文章目录1. unordered_map的介绍和使用🍑 unordered_map的构造🍑 unordered_map的使用🍅 insert🍅 operator[ ]🍅 find🍅 erase🍅 size🍅 empty🍅 clear🍅 sw…...
Android无菜单键,如何触发onCreateOptionsMenu(Menu menu)
文章目录小结问题及解决无法触发onCreateOptionsMenu(Menu menu)修改配置文件解决使用一个按钮来触发其它办法参考小结 现在的Android有三个键: 任务键,Home键,返回键,也就是没有菜单键了,那么如何如何触发onCreateOp…...
“黑洞”竟是外星人的量子计算机?
宇宙中的黑洞可以用作终极量子计算机,我们可以从中探索它们的特征。(图片来源:网络)我们完全有理由怀疑生命在我们的宇宙中很常见,但是为什么我们从未发现过其他生命存在的迹象?这个问题几乎自现代天文学诞…...
计算机网络入门
一,计算机网络在信息时代中的作用 21世纪的一些重要特征就是数字化,网络化和信息化,它是一个以网络为核心的信息时代。有三类大家很熟悉的网络,即电信网络,有线电视网络和计算机网络。按照最初的服务分工,…...
网络安全-内网DNS劫持-ettercap
网络安全-内网DNS劫持-ettercap 前言 一,我也是初学者记录的笔记 二,可能有错误的地方,请谨慎 三,欢迎各路大神指教 四,任何文章仅作为学习使用 五,学习网络安全知识请勿适用于违法行为 学习网络安全知识请…...
synchronized和Lock的区别
synchronized和lock的区别 synchronized和Lock,我已经通过源码级别的介绍过了,下面我们来总结下他们的区别 区别: 1.synchronized是关键字,Lock是接口,synchronized是JVM层实现,Lock是JDK中JUC包下的实现;…...
SpringBoot 指标监控 Actuator
Spring Boot Actuator为 Micrometer 提供了依赖管理和自动配置,Micrometer是一个支持 众多监控系统 的应用程序指标接口 该功能与:java\jdk\bin 下的 Jconsole 功能雷同 1、pom文件中引入依赖(使用的springboot是2.7.2) <dep…...
面试浅谈之十大排序算法
面试浅谈之十大排序算法 HELLO,各位博友好,我是阿呆 🙈🙈🙈 这里是面试浅谈系列,收录在专栏面试中 😜😜😜 本系列将记录一些阿呆个人整理的面试题 🏃&…...
LeetCode-1250. 检查「好数组」【数论,裴蜀定理】
LeetCode-1250. 检查「好数组」【数论,裴蜀定理】题目描述:解题思路一:裴蜀定理是:a*xb*y1。其中a,b是数组中的数,x,y是任意整数。如果a,b互质那么一定有解。问题即转换为寻找互质的数。解题思路二:简化代码…...
【Linux】NTP时间同步服务与NFS网络文件共享存储服务器(配置、测试)
一、NTP时间同步服务1、NTP介绍NTP服务器【Network Time Protocol(NTP)】是用来使计算机时间同步化的一种协议,它可以使计机对其服务器或时钟源(如石英钟,GPS等等)做同步化,它可以提供高精准度的时间校正&a…...
windows下php连接oracle安装oci8扩展报错(PHP Startup: Unable to load dynamic library ‘oci8_11g‘)
记录一下php7.29安装oci8的艰苦过程,简直就是唐僧西天取经历经九九八十一难。 使用的是phpstudy_pro安装的ph扩展wnmp环境下; 1 、安装oralce Instant Client 首先,安装oci8和pdo_oci扩展依赖的Oracle client。了解到需要连接的Oracle版…...
TensorRT的功能
TensorRT的功能 文章目录TensorRT的功能2.1. C and Python APIs2.2. The Programming Model2.2.2. The Runtime Phase2.3. Plugins2.4. Types and Precision2.5. Quantization2.6. Tensors and Data Formats2.7. Dynamic Shapes2.8. DLA2.9. Updating Weights2.10. trtexec本章…...
UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
