首页/新闻资讯/正文详情

反转链表:3步走通2种实现,迭代与递归一篇讲透

发布时间:2026/11/5 3:22:13 来源:云帆数科 栏目:资讯中心
反转链表:3步走通2种实现,迭代与递归一篇讲透
反转链表3步走通2种实现迭代与递归一篇讲透【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址: https://gitcode.com/gh_mirrors/al/algorithm-base反转链表Reverse Linked List是刷链表题绕不开的第一道关思路一听就懂但自己一写就总在手忙脚乱中把链弄丢。本文基于 algorithm-base 项目的链表篇教程带你先建立指针逐个掉头的心智模型再分别拆解迭代和递归两种实现最后给出选型建议和练习路线帮你把这道题真正变成基本功。30秒直觉用一句话建立心智模型反转链表就是从头走到尾边走边把每个节点的箭头拧到身后走完时最后一个节点自然成了新头。反转前1 - 2 - 3 - None 反转后None - 1 - 2 - 3 3 成为新头注意一个前提题目只允许修改节点的指向不允许改节点的值。所以倒着取节点拼一条新链这类思路是走不通的我们只能动箭头。方法A三指针迭代从前往后逐个掉头先看懂掉头这个动作大白话每个节点原本指向下一个人反转就是让它改口指向上一个人。做这件事只需要三个角色——prev已反转部分的头起点时是 None即新链表的尾巴cur当前正要掉头的节点nxt临时记住cur的下一个防止掉头后找不到路三个指针如何一步步推进以1 - 2 - 3为例跟着走三轮 看prev | cur的分隔线在哪初始 None | 1 - 2 - 3 - None prev cur 第1轮后1 掉头指向 None None | 1 | 2 - 3 - None prev cur 1.next None 第2轮后2 掉头指向 1 None - 1 | 2 | 3 - None prev cur 第3轮后3 掉头指向 2 None - 1 - 2 | 3 prev cur cur 走完变 Noneprev 停在 3它就是新头。整个过程prev永远走在已处理的一侧cur永远走在待处理的一侧两者的分界线每次后移一格这就是迭代反转的全部节奏。逐轮该做哪四件事每轮固定四步顺序不能乱nxt cur.next先记住下一个节点这一步不做链表当场断掉cur.next prev当前节点掉头指向已反转部分prev cur分界线右移当前节点并入已反转部分cur nxt进入下一轮Python 实现class Solution: def reverseList(self, head: ListNode) - ListNode: prev None # 已反转部分的头初始为空 cur head # 待反转部分的头 while cur: nxt cur.next # 1. 先存下一个防止断链 cur.next prev # 2. 当前节点掉头 prev cur # 3. 分界线右移 cur nxt # 4. 处理下一个节点 return prev # cur 走完prev 即新头空链表和单节点不需要特判循环要么不执行返回 None要么走一轮就结束返回唯一节点天然覆盖了边界。方法B递归从尾部开始才顺为什么先去尾巴换个角度看这道题如果让你从后往前处理反转反而很自然——最后一个节点不用动它就是新头倒数第二个指向它……难点在于单链表只能从前往后走而递归恰好能帮你先冲到尾巴。这就是递归写法的切入点把掉头推迟到回来的路上做。返回路上如何完成翻转还是以1 - 2 - 3为例下行递f(1) - f(2) - f(3) 3 是最后一个节点命中基准条件直接返回 3 上行归 回到 f(2)3.next 2然后 2.next None 得到 3 - 2 回到 f(1)2.next 1然后 1.next None 得到 3 - 2 - 1关键两行head.next.next head让下一个节点回指自己和head.next None切断旧方向防止两个节点互相指成环就是上行时每个节点要做的全部事情。逐行该做哪三件事命中基准条件head为 None 或只剩一个节点它自己就是子链的新头原样返回new_head self.reverseList(head.next)把剩下的事交给尾部拿到反转后子链的新头head.next.next head且head.next None把当前节点挂到子链前面并断开旧方向return new_head每一层都返回同一个最终新头保证最外层拿到的也是它Python 实现class Solution: def reverseList(self, head: ListNode) - ListNode: # 基准空链或最后一节点自己就是新头 if head is None or head.next is None: return head new_head self.reverseList(head.next) # 先反转尾部 head.next.next head # 让下一个节点回指自己 head.next None # 切断旧方向防环 return new_head迭代和递归的行数差不多但递归把记下一个节点、移动两个指针压缩成了一次调用和两行赋值读起来更紧凑。两种实现怎么选维度三指针迭代递归时间复杂度O(n)每个节点访问一次O(n)每个节点访问一次空间复杂度O(1)只用了几个指针变量O(n)调用栈深度等于链表长度出错风险点四步顺序别乱尤其先存nxt理解下行不动、上行才反转长链表表现稳定链表过长时可能栈溢出代码观感略繁琐但直白更紧凑选型建议默认写迭代。空间 O(1)、不怕长链机试和日常题里它最省心。递归适合两个场合面试官明确想听递归思路时以及后面要写 K 个一组反转LeetCode 25这类题时按组切分 递归下探的结构会比迭代好写很多。延伸两个常见的变形入口只反转一段LeetCode 92 反转链表 II。入口是定位 局部反转 重新接回先走到第left个节点前把left..right这段用上面的三指针法原样反转最后把断开的两头接回去。难点不在反转本身而在两头重接时别丢指针。项目里有对应的分步解析animation-simulation/链表篇/leetcode92反转链表2.md。K 个一组反转LeetCode 25。思路是把链表看成若干块每块凑够 K 个就整块反转凑不够保持原样。单块反转直接复用三指针法块与块之间递归处理。掌握 206 之后这道题的增量部分只是分组和拼接。动手练习路线先闭卷手写迭代版哪怕花二十分钟重点确认那四步的顺序能自己默出来对照动画自查打开项目里的 完整动画教程逐轮核对每轮结束后prev和cur的位置是否和你手写时推演的一致提交验证边界空链表、单节点、两节点三种输入各跑一遍再提交 LeetCode顺带把递归版默写一遍卡壳就回看下行不动、上行才反转那节更多链表题可以逛 animation-simulation/链表篇/反转链表这道题没有捷径就是把存下一个、掉头、移分界这个循环在脑子里过成肌肉记忆。接下来建议直接上手 LeetCode 92把局部反转的拼接练熟K 个一组反转水到渠成。【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址: https://gitcode.com/gh_mirrors/al/algorithm-base创作声明:本文部分内容由AI辅助生成(AIGC),仅供参考

相关推荐

如何用 KeymouseGo 自动操作鼠标键盘:从录制到回放的完整教程
如何用 KeymouseGo 自动操作鼠标键盘:从录制到回放的完整教程

如何用 KeymouseGo 自动操作鼠标键盘:从录制到回放的完整教程 【免费下载链接】KeymouseGo 类似按键精灵的鼠标键盘录制和自动化操作 模拟点击和键入 | automate mouse clicks and keyboard input 项目地址: https://gitcode.com/gh_mirrors/ke/KeymouseGo 假… · 2026/11/5 3:22:13

【电气开发】[常见电气元件选型使用]
【电气开发】[常见电气元件选型使用]

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 3:22:13

使用el-upload添加除预览+删除之外的功能图标按钮
使用el-upload添加除预览+删除之外的功能图标按钮

**需求&#xff1a;**使用el-upload添加除预览删除之外的添加索引设置小图标按钮 实现效果如图&#xff1a;分别为未添加图片、添加图片、添加图片为设置限制数量5时添加按钮隐藏结构代码如下&#xff1a; <el-form-item label"图片&#xff1a;" prop"gasPr… · 2026/11/5 3:22:13

KytyPS5 完整指南:在 PC 上构建并运行 PS5 游戏
KytyPS5 完整指南:在 PC 上构建并运行 PS5 游戏

KytyPS5 完整指南&#xff1a;在 PC 上构建并运行 PS5 游戏 【免费下载链接】KytyPS5 PlayStation 5 translation layer for Windows, Linux and macOS 项目地址: https://gitcode.com/gh_mirrors/ky/KytyPS5 KytyPS5 是一款免费开源的 PS5 模拟器&#xff0c;用 C 编写… · 2026/11/5 5:07:59

免费上手 3D 高斯斑点编辑:SuperSplat 快速使用指南
免费上手 3D 高斯斑点编辑:SuperSplat 快速使用指南

免费上手 3D 高斯斑点编辑&#xff1a;SuperSplat 快速使用指南 【免费下载链接】super-splat 3D Gaussian Splat Editor 项目地址: https://gitcode.com/gh_mirrors/su/super-splat SuperSplat 是一款免费、开源、完全运行在浏览器里的 3D 高斯斑点编辑工具&#xff0c… · 2026/11/5 5:07:59

ORM 编程思想及应用程序分层
ORM 编程思想及应用程序分层

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 5:07:59

LXGW WenKai 霞鹜文楷免费商用开源楷体中文字体:6 个 TTF 文件、2 万余汉字,3 分钟装进系统
LXGW WenKai 霞鹜文楷免费商用开源楷体中文字体:6 个 TTF 文件、2 万余汉字,3 分钟装进系统

LXGW WenKai 霞鹜文楷免费商用开源楷体中文字体&#xff1a;6 个 TTF 文件、2 万余汉字&#xff0c;3 分钟装进系统 【免费下载链接】LxgwWenKai An open-source Chinese font derived from Fontworks Klee One. 一款开源中文字体&#xff0c;基于 FONTWORKS 出品字体 Klee One… · 2026/11/5 5:07:59

Ideon路线图与社区:如何参与这个开源无限画布项目的开发
Ideon路线图与社区:如何参与这个开源无限画布项目的开发

【免费下载链接】ideon Your project is scattered across too many tools. Map the chaos on an infinite canvas where notes, files, TO-DOs (and more!) finally live together. 项目地址&#xff1a; https://gitcode.com/gh_mirrors/id/ideon 点击查看 免费下载 Ideon 是… · 2026/11/5 5:07:59

基于ADS122U04与STM32L452RE的PT100高精度测温方案
基于ADS122U04与STM32L452RE的PT100高精度测温方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 5:06:59

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 3:16:49

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 6:59:29

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 7:02:38

多智能体协作系统架构设计与实践优化
多智能体协作系统架构设计与实践优化

1. 多智能体协作系统的时代背景2017年Transformer架构的诞生彻底改变了人工智能的发展轨迹。当行业还沉浸在单一大模型带来的性能突破时&#xff0c;Anthropic的研究团队已经将目光投向了更前沿的领域——如何让多个智能体通过协作产生超越单体能力的系统智能。这就像交响乐团中… · 2026/11/5 0:00:39

大模型系统性入门实战指南:从原理到部署微调的全链路路线
大模型系统性入门实战指南:从原理到部署微调的全链路路线

提到大模型的系统性入门&#xff0c;我先说个结论&#xff1a;这事真不难&#xff0c;难的是资料太散、路线太多&#xff0c;今天这个框架明天那个工具&#xff0c;新人很容易在“收藏夹吃灰”和“教程看到一半放弃”之间反复横跳。市面上关于大模型的内容少说有几十万篇&#… · 2026/11/5 0:00:39

鸿蒙文件系统沙箱机制解析与开发实践
鸿蒙文件系统沙箱机制解析与开发实践

1. 鸿蒙文件系统沙箱机制深度解析作为一名从Android转向鸿蒙开发的工程师&#xff0c;我深刻体会到文件系统访问是迁移过程中最先遇到的"拦路虎"。在Android上运行良好的文件读写代码&#xff0c;在鸿蒙真机环境却频频出现文件写入后神秘消失或直接抛出权限拒绝错误的… · 2026/11/5 0:00:39

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 3:16:49

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 6:59:29

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 7:02:38

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码