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

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:指向当前节点的下一个节点。
  • 遍历链表,逐个反转节点的指向。
步骤
  1. 初始化 prev = Nonecurr = head
  2. 遍历链表:
    • 保存 curr 的下一个节点:next = curr.next
    • 反转当前节点的指向:curr.next = prev
    • 移动 prevcurrprev = currcurr = next
  3. 遍历结束后,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:递归法

核心思想
  • 递归地反转链表:
    • 递归到链表的最后一个节点,将其作为新的头节点。
    • 在回溯过程中,逐个反转节点的指向。
步骤
  1. 递归终止条件:如果链表为空或只有一个节点,直接返回 head
  2. 递归调用:反转 head.next 之后的链表。
  3. 反转当前节点的指向:head.next.next = head
  4. 断开当前节点的指向:head.next = None
  5. 返回新的头节点。
代码实现
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 引言 本节常见面试题 如何判断对象是否死亡&#xff08;两种方法&#xff09;。简单的介绍一下强引用、软引用、弱引用、虚引用&#xff08;虚引用与软引用和弱引用的区别、使用软引用能带来的好处&#xff09;。如何判断一个常量是废弃常量如何判断一个类是无用的类垃圾收…...

【简单】209.长度最小的子数组

题目描述 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl1, …, numsr-1, numsr] &#xff0c;并返回其长度。如果不存在符合条件的子数组&#xff0c;返回0。 示例 1&#xff1a; 输入&am…...

细说 Java 引用(强、软、弱、虚)和 GC 流程(二)

一、前文回顾 在 细说Java 引用&#xff08;强、软、弱、虚&#xff09;和 GC 流程&#xff08;一&#xff09; 我们对Java 引用有了总体的认识&#xff0c;本文将继续深入分析 Java 引用在 GC 时的一些细节。 还是从我们在前文中提到的引用流程图里说起&#xff0c;这里不清…...

CSS通过webkit-scrollbar设置滚动条样式

查看::-webkit-scrollbar-*各项关系 以下图为例&#xff0c;可以分别定义滚动条背景、滚动轨道、滚动滑块的样式。 需要先给外部容器设置高度&#xff0c;再设置overflow: auto&#xff0c;最后设置三个webkit属性。 <!DOCTYPE html> <html lang"en">…...

Win10配置VSCode的C/C++编译环境

GNU&#xff08;编译器工具集合&#xff09;包含了g、gcc和gdb等编译器。MinGW&#xff08;Minimalist GNU for Windows&#xff09;是一个适用于Windows操作系统的最小化的GNU工具集&#xff0c;它包括了GCC编译器&#xff08;包括g&#xff09;以及其他一些必要的库和工具。M…...

数据结构与算法再探(七)查找-排序

查找 一、二分查找 二分查找是一种高效的查找算法&#xff0c;适用于在已排序的数组或列表中查找特定元素。它通过将搜索范围逐步减半来快速定位目标元素。理解二分查找的“不变量”和选择左开右闭区间的方式是掌握这个算法的关键。 二分查找关键点 不变量 在二分查找中&a…...

【C语言】指针(5)

前言&#xff1a;上篇文章的末尾我们使用了转移表来解决代码冗余的问题&#xff0c;那我们还有没有什么办法解决代码冗余呢&#xff1f;有的这就是接下来要说的回调函数。 往期文章: 指针1 指针2 指针3 指针4 文章目录 一&#xff0c;回调函数二&#xff0c;qsort实现快速排序1…...

大数据组件(四)快速入门实时数据湖存储系统Apache Paimon(2)

Paimon的下载及安装&#xff0c;并且了解了主键表的引擎以及changelog-producer的含义参考&#xff1a; 大数据组件(四)快速入门实时数据湖存储系统Apache Paimon(1) 利用Paimon表做lookup join&#xff0c;集成mysql cdc等参考&#xff1a; 大数据组件(四)快速入门实时数据…...

PLC通讯

PPI通讯 是西门子公司专为s7-200系列plc开发的通讯协议。内置于s7-200 CPU中。PPI协议物理上基于RS-485口&#xff0c;通过屏蔽双绞线就可以实现PPI通讯。PPI协议是一种主-从协议。主站设备发送要求到从站设备&#xff0c;从站设备响应&#xff0c;从站不能主动发出信息。主站…...

前端js进阶,ES6语法,包详细

进阶ES6 作用域的概念加深对js理解 let、const申明的变量&#xff0c;在花括号中会生成块作用域&#xff0c;而var就不会生成块作用域 作用域链本质上就是底层的变量查找机制 作用域链查找的规则是:优先查找当前作用域先把的变量&#xff0c;再依次逐级找父级作用域直到全局…...

Scrum方法论指导下的Deepseek R1医疗AI部署开发

一、引言 1.1 研究背景与意义 在当今数智化时代&#xff0c;软件开发方法论对于项目的成功实施起着举足轻重的作用。Scrum 作为一种广泛应用的敏捷开发方法论&#xff0c;以其迭代式开发、快速反馈和高效协作的特点&#xff0c;在软件开发领域占据了重要地位。自 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 项目背景 在信息高速流通的当下&#xff0c;新闻媒体行业每天都要处理和传播海量信息。传统的新闻管理模式依赖人工操作&#xff0c;在新闻采集、编辑、发布以及后续管理等环节中&#xff0c;不仅效率低下&#xff0c;而且容易出现人为失误。同时&#xff0…...

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、反射机制定义及作用 反射是允许程序在运行时检查和操作类、方法、属性等的机制&#xff0c;能够动态地获取信息、调用方法等。换句话说&#xff0c;在编写程序时&#xff0c;不需要知道要操作的类的具体信息&#xff0c;而是在程序运行时获取和使用。 2、反射机制…...

java实现二维码图片生成和编解码

java实现二维码图片生成和编解码 在wutool中&#xff0c;封装了二维码工具类&#xff0c;基于google的zxing库&#xff0c;实现二维码图片生成、编码和解码。 关于wutool wutool是一个java代码片段收集库&#xff0c;针对特定场景提供轻量解决方案&#xff0c;只要按需选择代…...

Java基础常见的面试题(易错!!)

面试题一&#xff1a;为什么 Java 不支持多继承 Java 不支持多继承主要是为避免 “菱形继承问题”&#xff08;又称 “钻石问题”&#xff09;&#xff0c;即一个子类从多个父类继承到同名方法或属性时&#xff0c;编译器无法确定该调用哪个父类的成员。同时&#xff0c;多继承…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...