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 不支持多继承主要是为避免 “菱形继承问题”(又称 “钻石问题”),即一个子类从多个父类继承到同名方法或属性时,编译器无法确定该调用哪个父类的成员。同时,多继承…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...
GitFlow 工作模式(详解)
今天再学项目的过程中遇到使用gitflow模式管理代码,因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存,无论是github还是gittee,都是一种基于git去保存代码的形式,这样保存代码…...
云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
02.运算符
目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&:逻辑与 ||:逻辑或 !:逻辑非 短路求值 位运算符 按位与&: 按位或 | 按位取反~ …...
车载诊断架构 --- ZEVonUDS(J1979-3)简介第一篇
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 做到欲望极简,了解自己的真实欲望,不受外在潮流的影响,不盲从,不跟风。把自己的精力全部用在自己。一是去掉多余,凡事找规律,基础是诚信;二是…...
Python学习(8) ----- Python的类与对象
Python 中的类(Class)与对象(Object)是面向对象编程(OOP)的核心。我们可以通过“类是模板,对象是实例”来理解它们的关系。 🧱 一句话理解: 类就像“图纸”,对…...
