LeetCode 热题 100 206. 反转链表
LeetCode 热题 100 | 206. 反转链表
大家好,今天我们来解决一道经典的算法题——反转链表。这道题在 LeetCode 上被标记为简单难度,要求我们将一个单链表反转,并返回反转后的链表。下面我将详细讲解解题思路,并附上 Python 代码实现。
题目描述
给定单链表的头节点 head,反转链表,并返回反转后的链表。
示例:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
解题思路
反转链表的核心思想是改变链表中节点的指向关系,将每个节点的 next 指针指向前一个节点。我们可以通过 迭代 或 递归 两种方法来实现。
方法 1:迭代法
核心思想
- 使用三个指针:
prev:指向当前节点的前一个节点,初始为None。curr:指向当前节点,初始为head。next:指向当前节点的下一个节点。
- 遍历链表,逐个反转节点的指向。
步骤
- 初始化
prev = None,curr = head。 - 遍历链表:
- 保存
curr的下一个节点:next = curr.next。 - 反转当前节点的指向:
curr.next = prev。 - 移动
prev和curr:prev = curr,curr = next。
- 保存
- 遍历结束后,
prev就是反转后的链表的头节点。
代码实现
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef reverseList(head):prev = None # 前一个节点curr = head # 当前节点while curr:next = curr.next # 保存下一个节点curr.next = prev # 反转当前节点的指向prev = curr # 移动 prevcurr = next # 移动 currreturn prev # 返回反转后的头节点
复杂度分析
- 时间复杂度:O(n),其中 n 是链表的长度。需要遍历链表一次。
- 空间复杂度:O(1),只使用了常数个额外空间。
方法 2:递归法
核心思想
- 递归地反转链表:
- 递归到链表的最后一个节点,将其作为新的头节点。
- 在回溯过程中,逐个反转节点的指向。
步骤
- 递归终止条件:如果链表为空或只有一个节点,直接返回
head。 - 递归调用:反转
head.next之后的链表。 - 反转当前节点的指向:
head.next.next = head。 - 断开当前节点的指向:
head.next = None。 - 返回新的头节点。
代码实现
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef reverseList(head):# 递归终止条件if not head or not head.next:return head# 递归反转剩余链表new_head = reverseList(head.next)# 反转当前节点的指向head.next.next = headhead.next = None# 返回新的头节点return new_head
复杂度分析
- 时间复杂度:O(n),其中 n 是链表的长度。需要递归调用 n 次。
- 空间复杂度:O(n),递归调用栈的深度为 n。
示例运行
示例 1
# 创建链表 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)# 反转链表
reversed_head = reverseList(head)# 输出反转后的链表
while reversed_head:print(reversed_head.val, end=" -> ")reversed_head = reversed_head.next
print("None")
输出:
5 -> 4 -> 3 -> 2 -> 1 -> None
示例 2
# 创建链表 1 -> 2
head = ListNode(1)
head.next = ListNode(2)# 反转链表
reversed_head = reverseList(head)# 输出反转后的链表
while reversed_head:print(reversed_head.val, end=" -> ")reversed_head = reversed_head.next
print("None")
输出:
2 -> 1 -> None
示例 3
# 创建空链表
head = None# 反转链表
reversed_head = reverseList(head)# 输出反转后的链表
while reversed_head:print(reversed_head.val, end=" -> ")reversed_head = reversed_head.next
print("None")
输出:
None
总结
- 迭代法:通过遍历链表,逐个反转节点的指向,时间复杂度为 O(n),空间复杂度为 O(1)。
- 递归法:通过递归调用反转链表,时间复杂度为 O(n),空间复杂度为 O(n)。
- 两种方法都能高效地解决反转链表的问题,选择哪种方法取决于具体需求和场景。
希望这篇题解对你有帮助!如果还有其他问题,欢迎继续提问!
关注我,获取更多算法题解和编程技巧!
相关文章:
LeetCode 热题 100 206. 反转链表
LeetCode 热题 100 | 206. 反转链表 大家好,今天我们来解决一道经典的算法题——反转链表。这道题在 LeetCode 上被标记为简单难度,要求我们将一个单链表反转,并返回反转后的链表。下面我将详细讲解解题思路,并附上 Python 代码实…...
2025年02月21日Github流行趋势
项目名称:source-sdk-2013 项目地址url:https://github.com/ValveSoftware/source-sdk-2013项目语言:C历史star数:7343今日star数:929项目维护者:JoeLudwig, jorgenpt, narendraumate, sortie, alanedwarde…...
WebXR教学 03 项目1 旋转彩色方块
一、项目结构 webgl-cube/ ├── index.html ├── main.js ├── package.json └── vite.config.js二、详细实现步骤 初始化项目 npm init -y npm install three vite --save-devindex.html <!DOCTYPE html> <html lang"en"> <head><…...
深入解析JVM垃圾回收机制
1 引言 本节常见面试题 如何判断对象是否死亡(两种方法)。简单的介绍一下强引用、软引用、弱引用、虚引用(虚引用与软引用和弱引用的区别、使用软引用能带来的好处)。如何判断一个常量是废弃常量如何判断一个类是无用的类垃圾收…...
【简单】209.长度最小的子数组
题目描述 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回0。 示例 1: 输入&am…...
细说 Java 引用(强、软、弱、虚)和 GC 流程(二)
一、前文回顾 在 细说Java 引用(强、软、弱、虚)和 GC 流程(一) 我们对Java 引用有了总体的认识,本文将继续深入分析 Java 引用在 GC 时的一些细节。 还是从我们在前文中提到的引用流程图里说起,这里不清…...
CSS通过webkit-scrollbar设置滚动条样式
查看::-webkit-scrollbar-*各项关系 以下图为例,可以分别定义滚动条背景、滚动轨道、滚动滑块的样式。 需要先给外部容器设置高度,再设置overflow: auto,最后设置三个webkit属性。 <!DOCTYPE html> <html lang"en">…...
Win10配置VSCode的C/C++编译环境
GNU(编译器工具集合)包含了g、gcc和gdb等编译器。MinGW(Minimalist GNU for Windows)是一个适用于Windows操作系统的最小化的GNU工具集,它包括了GCC编译器(包括g)以及其他一些必要的库和工具。M…...
数据结构与算法再探(七)查找-排序
查找 一、二分查找 二分查找是一种高效的查找算法,适用于在已排序的数组或列表中查找特定元素。它通过将搜索范围逐步减半来快速定位目标元素。理解二分查找的“不变量”和选择左开右闭区间的方式是掌握这个算法的关键。 二分查找关键点 不变量 在二分查找中&a…...
【C语言】指针(5)
前言:上篇文章的末尾我们使用了转移表来解决代码冗余的问题,那我们还有没有什么办法解决代码冗余呢?有的这就是接下来要说的回调函数。 往期文章: 指针1 指针2 指针3 指针4 文章目录 一,回调函数二,qsort实现快速排序1…...
大数据组件(四)快速入门实时数据湖存储系统Apache Paimon(2)
Paimon的下载及安装,并且了解了主键表的引擎以及changelog-producer的含义参考: 大数据组件(四)快速入门实时数据湖存储系统Apache Paimon(1) 利用Paimon表做lookup join,集成mysql cdc等参考: 大数据组件(四)快速入门实时数据…...
PLC通讯
PPI通讯 是西门子公司专为s7-200系列plc开发的通讯协议。内置于s7-200 CPU中。PPI协议物理上基于RS-485口,通过屏蔽双绞线就可以实现PPI通讯。PPI协议是一种主-从协议。主站设备发送要求到从站设备,从站设备响应,从站不能主动发出信息。主站…...
前端js进阶,ES6语法,包详细
进阶ES6 作用域的概念加深对js理解 let、const申明的变量,在花括号中会生成块作用域,而var就不会生成块作用域 作用域链本质上就是底层的变量查找机制 作用域链查找的规则是:优先查找当前作用域先把的变量,再依次逐级找父级作用域直到全局…...
Scrum方法论指导下的Deepseek R1医疗AI部署开发
一、引言 1.1 研究背景与意义 在当今数智化时代,软件开发方法论对于项目的成功实施起着举足轻重的作用。Scrum 作为一种广泛应用的敏捷开发方法论,以其迭代式开发、快速反馈和高效协作的特点,在软件开发领域占据了重要地位。自 20 世纪 90 …...
LINUX安装使用Redis
参考 Install Redis on Linux | Docs 安装命令 sudo apt-get install -y lsb-release curl gpgcurl -fsSL https://packages.redis.io/gpg | sudo gpg --dearmor -o /usr/share/keyrings/redis-archive-keyring.gpgsudo chmod 644 /usr/share/keyrings/redis-archive-keyrin…...
基于java新闻管理系统,推荐一款开源cms内容管理系统ruoyi-fast-cms
一、项目概述 1.1 项目背景 在信息高速流通的当下,新闻媒体行业每天都要处理和传播海量信息。传统的新闻管理模式依赖人工操作,在新闻采集、编辑、发布以及后续管理等环节中,不仅效率低下,而且容易出现人为失误。同时࿰…...
054 redisson
文章目录 使用Redisson演示可重入锁读写锁信号量闭锁获取三级分类redisson分布式锁 package com.xd.cubemall.product.config;import org.redisson.Redisson; import org.redisson.api.RedissonClient; import org.redisson.config.Config; import org.springframework.context…...
【数据结构】(12) 反射、枚举、lambda 表达式
一、反射 1、反射机制定义及作用 反射是允许程序在运行时检查和操作类、方法、属性等的机制,能够动态地获取信息、调用方法等。换句话说,在编写程序时,不需要知道要操作的类的具体信息,而是在程序运行时获取和使用。 2、反射机制…...
java实现二维码图片生成和编解码
java实现二维码图片生成和编解码 在wutool中,封装了二维码工具类,基于google的zxing库,实现二维码图片生成、编码和解码。 关于wutool wutool是一个java代码片段收集库,针对特定场景提供轻量解决方案,只要按需选择代…...
Java基础常见的面试题(易错!!)
面试题一:为什么 Java 不支持多继承 Java 不支持多继承主要是为避免 “菱形继承问题”(又称 “钻石问题”),即一个子类从多个父类继承到同名方法或属性时,编译器无法确定该调用哪个父类的成员。同时,多继承…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...
HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...
go 里面的指针
指针 在 Go 中,指针(pointer)是一个变量的内存地址,就像 C 语言那样: a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10,通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...
【WebSocket】SpringBoot项目中使用WebSocket
1. 导入坐标 如果springboot父工程没有加入websocket的起步依赖,添加它的坐标的时候需要带上版本号。 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId> </dep…...
js 设置3秒后执行
如何在JavaScript中延迟3秒执行操作 在JavaScript中,要设置一个操作在指定延迟后(例如3秒)执行,可以使用 setTimeout 函数。setTimeout 是JavaScript的核心计时器方法,它接受两个参数: 要执行的函数&…...
C++ 类基础:封装、继承、多态与多线程模板实现
前言 C 是一门强大的面向对象编程语言,而类(Class)作为其核心特性之一,是理解和使用 C 的关键。本文将深入探讨 C 类的基本特性,包括封装、继承和多态,同时讨论类中的权限控制,并展示如何使用类…...
