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

力扣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&#xff1a;非递归方法2&#xff1a;递归力扣24.两两交换链表中的节点 题目描述 给你一个链表&#xff0c;两两交换其中相邻的节点&#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题&…...

AtCoder Regular Contest 137 题解(A~C)

A-Coprime Pair 思路 我们知道两个质数之间并不会相隔太远&#xff0c;于是我们直接用暴力就可以通过这题。 先从大到小枚举答案&#xff0c;并且枚举所有可能的起点&#xff0c;当枚举到的两个值满足条件输出并结束程序即可。 代码 #include <bits/stdc.h> using n…...

【C语言】预处理指令

C语言预处理指令一、什么是预处理指令二、预处理指令特点三、文件包含四、C标准库<stdio.h>一、什么是预处理指令 C语言的源文件&#xff08;.c文件&#xff09;需要经过编译生成可执行程序&#xff0c;编译操作会将源文件转换成目标文件&#xff0c;对于 VC、VS&#x…...

Java基础之多线程JUC全面学习笔记

目录初识多线程多线程的实现方式常见的成员方法线程安全的问题死锁生产者和消费者线程池自定义线程池初识多线程 什么是多线程? 线程 线程是操作系统能够进行运算调度的最小单位。线程被包含在进程之中&#xff0c;是进程中的实际运作单位。 简单理解:应用软件中互相独立&…...

13.CSS文本样式

文本样式 h1 {color: blue; }● 回顾上一节的内容&#xff0c;我们让h1标题的文字变成了蓝色&#xff0c;注意如果html中有多个h1标签&#xff0c;那我们这种写法所有的h1标签都会变成蓝色&#xff0c;除了颜色&#xff0c;本节我们将学习更多的CSS属性 文字大小font-size h…...

西恩科技更新招股书:IPO前大手笔分红“套现”, 赵志安为实控人

2月14日&#xff0c;上海西恩科技股份有限公司&#xff08;下称“西恩科技”&#xff09;更新了招股书&#xff08;申报稿&#xff09;。据贝多财经了解&#xff0c;西恩科技于2022年8月12日递交上市申请材料&#xff0c;准备在创业板上市&#xff0c;此次是西恩科技第二次更新…...

【CentOS】有关时间的设置

目录环境信息date语法信息查看时间设置时间设置日期tzselecttimedatectl语法显示当前及所有时区修改时区hwclock语法读取硬件时钟使用硬件时钟设置系统时间使用系统时间设置硬件时钟如何理解硬件时钟和系统时钟环境信息 CentOS 7 date 语法信息 date --help用法&#xff1a…...

OpenCV制作Mask图像掩码

一、掩膜&#xff08;mask&#xff09; 在有些图像处理的函数中有的参数里面会有mask参数&#xff0c;即此函数支持掩膜操作&#xff0c;首先何为掩膜以及有什么用&#xff0c;如下&#xff1a; 数字图像处理中的掩膜的概念是借鉴于PCB制版的过程&#xff0c;在半导体制造中&am…...

C++STL剖析(九)—— unordered_map和unordered_multimap的概念和使用

文章目录1. unordered_map的介绍和使用&#x1f351; unordered_map的构造&#x1f351; unordered_map的使用&#x1f345; insert&#x1f345; operator[ ]&#x1f345; find&#x1f345; erase&#x1f345; size&#x1f345; empty&#x1f345; clear&#x1f345; sw…...

Android无菜单键,如何触发onCreateOptionsMenu(Menu menu)

文章目录小结问题及解决无法触发onCreateOptionsMenu(Menu menu)修改配置文件解决使用一个按钮来触发其它办法参考小结 现在的Android有三个键&#xff1a; 任务键&#xff0c;Home键&#xff0c;返回键&#xff0c;也就是没有菜单键了&#xff0c;那么如何如何触发onCreateOp…...

“黑洞”竟是外星人的量子计算机?

宇宙中的黑洞可以用作终极量子计算机&#xff0c;我们可以从中探索它们的特征。&#xff08;图片来源&#xff1a;网络&#xff09;我们完全有理由怀疑生命在我们的宇宙中很常见&#xff0c;但是为什么我们从未发现过其他生命存在的迹象&#xff1f;这个问题几乎自现代天文学诞…...

计算机网络入门

一&#xff0c;计算机网络在信息时代中的作用 21世纪的一些重要特征就是数字化&#xff0c;网络化和信息化&#xff0c;它是一个以网络为核心的信息时代。有三类大家很熟悉的网络&#xff0c;即电信网络&#xff0c;有线电视网络和计算机网络。按照最初的服务分工&#xff0c;…...

网络安全-内网DNS劫持-ettercap

网络安全-内网DNS劫持-ettercap 前言 一&#xff0c;我也是初学者记录的笔记 二&#xff0c;可能有错误的地方&#xff0c;请谨慎 三&#xff0c;欢迎各路大神指教 四&#xff0c;任何文章仅作为学习使用 五&#xff0c;学习网络安全知识请勿适用于违法行为 学习网络安全知识请…...

synchronized和Lock的区别

synchronized和lock的区别 synchronized和Lock&#xff0c;我已经通过源码级别的介绍过了&#xff0c;下面我们来总结下他们的区别 区别&#xff1a; 1.synchronized是关键字,Lock是接口&#xff0c;synchronized是JVM层实现&#xff0c;Lock是JDK中JUC包下的实现&#xff1b;…...

SpringBoot 指标监控 Actuator

Spring Boot Actuator为 Micrometer 提供了依赖管理和自动配置&#xff0c;Micrometer是一个支持 众多监控系统 的应用程序指标接口 该功能与&#xff1a;java\jdk\bin 下的 Jconsole 功能雷同 1、pom文件中引入依赖&#xff08;使用的springboot是2.7.2&#xff09; <dep…...

面试浅谈之十大排序算法

面试浅谈之十大排序算法 HELLO&#xff0c;各位博友好&#xff0c;我是阿呆 &#x1f648;&#x1f648;&#x1f648; 这里是面试浅谈系列&#xff0c;收录在专栏面试中 &#x1f61c;&#x1f61c;&#x1f61c; 本系列将记录一些阿呆个人整理的面试题 &#x1f3c3;&…...

LeetCode-1250. 检查「好数组」【数论,裴蜀定理】

LeetCode-1250. 检查「好数组」【数论&#xff0c;裴蜀定理】题目描述&#xff1a;解题思路一&#xff1a;裴蜀定理是&#xff1a;a*xb*y1。其中a,b是数组中的数&#xff0c;x,y是任意整数。如果a,b互质那么一定有解。问题即转换为寻找互质的数。解题思路二&#xff1a;简化代码…...

【Linux】NTP时间同步服务与NFS网络文件共享存储服务器(配置、测试)

一、NTP时间同步服务1、NTP介绍NTP服务器【Network Time Protocol&#xff08;NTP&#xff09;】是用来使计算机时间同步化的一种协议&#xff0c;它可以使计机对其服务器或时钟源&#xff08;如石英钟&#xff0c;GPS等等)做同步化&#xff0c;它可以提供高精准度的时间校正&a…...

windows下php连接oracle安装oci8扩展报错(PHP Startup: Unable to load dynamic library ‘oci8_11g‘)

记录一下php7.29安装oci8的艰苦过程&#xff0c;简直就是唐僧西天取经历经九九八十一难。 使用的是phpstudy_pro安装的ph扩展wnmp环境下&#xff1b; 1 、安装oralce Instant Client 首先&#xff0c;安装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本章…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...