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

反转链表:迭代与递归两种解法,含推演与复杂度对比

发布时间:2026/11/5 1:52:39 来源:云帆数科 栏目:资讯中心
反转链表:迭代与递归两种解法,含推演与复杂度对比
反转链表迭代与递归两种解法含推演与复杂度对比【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址: https://gitcode.com/gh_mirrors/al/algorithm-base模拟面试被问反转链表时我写完迭代版面试官追问递归怎么写我愣了一下——当时只是背过代码并没有想清楚指针在动什么。后来在 algorithm-base 项目里配合白板推演和动画教程把两种解法重新走了一遍才真正吃透。反转链表的核心思想把箭头逐个掉头单链表可以看作一排单行道每个节点只有一条出口——next 指针指向下一站。反转链表并不改动节点本身只是把每一条箭头的方向掉转过来原链表 1 → 2 → 3 → 4 → NULL 反转后 NULL ← 1 ← 2 ← 3 ← 4 即 4 → 3 → 2 → 1 → NULL有两种做法迭代是从入口开始一边前进一边把每段路掉头递归是先一路走到尽头回来时再逐个掉头。前者只靠两个辅助指针原地完成后者依赖调用栈来记住已经反到哪儿。下面分别推演。链表反转三指针推演与迭代实现用1 → 2 → 3 → 4做白板推演准备三个指针prev初值 NULL已反转部分的头cur初值 head待反转部分的头nxt临时在修改cur.next前保存后面的节点避免断链。每轮核心操作就是四行存nxt、把cur.next掉头指向prev、两个指针各前进一步。初始 NULL 1 → 2 → 3 → 4 prev cur 处理节点1后 NULL ← 1 2 → 3 → 4 prev cur 处理节点2后 NULL ← 1 ← 2 3 → 4 prev curcur走到 NULL 时所有箭头都已掉头此时prev恰好是新头。完整代码Pythonclass Solution: def reverseList(self, head: ListNode) - ListNode: prev, cur None, head while cur: nxt cur.next # 先存下一节点否则改写 cur.next 后就找不到路了 cur.next prev # 掉头当前节点指向已反转部分 prev, cur cur, nxt # 双指针前移反转部分每次扩大一个节点 return prev # 反转后的头空链表时自然返回 None项目里的反转链表动画教程把整个过程做成了逐步演示其中cur.next prev执行的那一刻正好对应推演表中处理节点1后这一步可以对照着逐步验证。教程内还有 Java、C、JavaScript、Swift、Go 五种语言的实现写法结构一致可一并参考。递归反转链表调用栈分析递归解法的关键是换到调用栈视角阅读下探阶段什么都不做一路钻到最后一个节点——这是基准条件它直接作为反转后的头返回回到阶段的每一层只做一件事让下一节点指回我我指向 NULL。以1 → 2 → 3为例reverseList(1) # 下探 └─ reverseList(2) └─ reverseList(3) → 返回 3 # 基准情况只剩一个节点原样返回 3.next 2断开 2 → 3 # 回溯3 掉头指向 2 2.next 1断开 1 → 2 # 回溯2 掉头指向 1 返回 3 # 每层只透传头节点不改变它Java 实现注意head.next必须在基准条件之后才允许访问class Solution { public ListNode reverseList(ListNode head) { // 基准条件空链表或最后一个节点它就是反转链的头 if (head null || head.next null) return head; ListNode newHead reverseList(head.next); // 先反转后面的链 head.next.next head; // 关键一步让下一节点反过来指当前节点 head.next null; // 断环否则前后两节点互相指向成环 return newHead; // 头节点不随递归层数变化原样向上透传 } }有三个高频易错点值得单独记一下忘记断环head.next.next head之后若不执行head.next null前两个节点会互为 next 形成环链表将无法遍历。基准条件漏掉空判断只写head.next null时传入空链表会直接空指针必须同时处理head null和单节点两种情况。返回值理解错误每层递归返回的newHead都是同一个原尾部节点而不是本段反转后的局部头返回成head就错了。两种解法的复杂度对比与选型解法时间复杂度空间复杂度特点迭代O(n)O(1)指针一趟走完无栈开销内存受限场景的首选递归O(n)O(n)调用栈深度代码更短走到尾再逐个掉头是链题常用套路面试作答建议先给出迭代版并讲清三个指针的职责这能覆盖常数额外空间的追问再补充一句递归版本质是调用栈回溯时逐个掉头并主动说明它的空间开销是 O(n)。两个方案都给出后选型问题基本闭环。反转链表的变形题破题点基础反转吃透后常见变形都是同一套思路的封装项目链表篇目录里有对应题目的动画可以对照区间反转链表LeetCode 92用哑节点定位到left前一位置对left到right这一段套用基础迭代反转再把两端接回去。只反转前 N 个节点写一个只反转前 N 个节点的辅助函数递归时逐层把反转部分的头返回给上层即可。K 个一组反转LeetCode 25每次先预探 K 个节点判断够不够一组够就反转该段并缝合首尾不够则原样保留。建议先在纸上默写两种解法逐步对照项目里的动画检查指针状态再开始刷变形题。下期讲讲链表的环检测与找环入口这两个经典问题。【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址: https://gitcode.com/gh_mirrors/al/algorithm-base创作声明:本文部分内容由AI辅助生成(AIGC),仅供参考

相关推荐

Godot 入门(08):撞墙判定,数组地图与边界
Godot 入门(08):撞墙判定,数组地图与边界

上一篇小人总算识行喇,不过佢有个毛病——会穿墙。 往左按十下,佢就由画面左边溜出去,连声招呼都唔打。 今日畀佢一张真正嘅地图,再教佢一件事:有啲地方,你去唔到。 一、地图不用画,敲几行字就行 做推箱子,最省事的地图不是画出来的,是敲出来的。 const MAP := [&qu… · 2026/11/5 1:52:39

8 款免费开源 Android 学习应用指南:按使用场景挑选
8 款免费开源 Android 学习应用指南:按使用场景挑选

8 款免费开源 Android 学习应用指南:按使用场景挑选 【免费下载链接】open-source-android-apps Open-Source Android Apps 项目地址: https://gitcode.com/gh_mirrors/op/open-source-android-apps 想在通勤、课间和睡前把碎片时间用起来,却不想… · 2026/11/5 1:51:39

免费实现原生分辨率串流:Apollo 桌面流的搭建与调优
免费实现原生分辨率串流:Apollo 桌面流的搭建与调优

免费实现原生分辨率串流:Apollo 桌面流的搭建与调优 【免费下载链接】Apollo Sunshine fork - The easiest way to stream with the native resolution of your client device 项目地址: https://gitcode.com/gh_mirrors/apollo18/Apollo Apollo 是一个基于 … · 2026/11/5 1:51:39

在macOS上安装OpenClaw并实现Chrome网站自动化测试_openclaw browser relay-CSDN博客
在macOS上安装OpenClaw并实现Chrome网站自动化测试_openclaw browser relay-CSDN博客

/* 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:31:15

MiniMax-H3 12G 显卡出带声音的视频:ComfyUI 部署完整实操
MiniMax-H3 12G 显卡出带声音的视频:ComfyUI 部署完整实操

MiniMax-H3 12G 显卡出带声音的视频:ComfyUI 部署完整实操 【免费下载链接】MiniMax-H3 项目地址: https://ai.gitcode.com/hf_mirrors/Comfy-Org/MiniMax-H3 MiniMax-H3 部署卡住的人,多半卡在三个点:选哪个精度版本、文件放哪个目录… · 2026/11/5 3:31:15

快速上手 nerdctl OverlayBD 懒加载:配置、验证与镜像转换完整指南
快速上手 nerdctl OverlayBD 懒加载:配置、验证与镜像转换完整指南

快速上手 nerdctl OverlayBD 懒加载:配置、验证与镜像转换完整指南 【免费下载链接】nerdctl contaiNERD CTL - Docker-compatible CLI for containerd, with support for Compose, Rootless, eStargz, OCIcrypt, IPFS, ... 项目地址: https://gitcode.com/gh_mir… · 2026/11/5 3:31:15

论文转PPT完整教程:nature-paper2ppt 如何快速把论文做成 10–16 页中文组会汇报 PPT
论文转PPT完整教程:nature-paper2ppt 如何快速把论文做成 10–16 页中文组会汇报 PPT

论文转PPT完整教程:nature-paper2ppt 如何快速把论文做成 10–16 页中文组会汇报 PPT 【免费下载链接】nature-skills 符合nature论文学术表达和科研绘图的Skill 项目地址: https://gitcode.com/gh_mirrors/na/nature-skills 组会前把一篇论文变成 15 分钟的… · 2026/11/5 3:31:15

5 分钟搭好自己的多平台直播录制系统:DouyinLiveRecorder 完整新手指南
5 分钟搭好自己的多平台直播录制系统:DouyinLiveRecorder 完整新手指南

5 分钟搭好自己的多平台直播录制系统:DouyinLiveRecorder 完整新手指南 【免费下载链接】DouyinLiveRecorder 可循环值守和多人录制的直播录制软件,支持抖音、TikTok、Youtube、快手、虎牙、斗鱼、B站、小红书、pandatv、sooplive、flextv、popkontv、tw… · 2026/11/5 3:31:15

Horizon AI新闻雷达:如何从信息过载中拯救你的时间?
Horizon AI新闻雷达:如何从信息过载中拯救你的时间?

Horizon AI新闻雷达:如何从信息过载中拯救你的时间? 【免费下载链接】Horizon 📡 Your own AI-powered news radar. Generates daily briefings in English & Chinese. | 用 AI 构建你专属的新闻雷达 项目地址: https://gitcode.com/Gi… · 2026/11/5 3:30:15

双极步进电机控制实战: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架构的诞生彻底改变了人工智能的发展轨迹。当行业还沉浸在单一大模型带来的性能突破时,Anthropic的研究团队已经将目光投向了更前沿的领域——如何让多个智能体通过协作产生超越单体能力的系统智能。这就像交响乐团中… · 2026/11/5 0:00:39

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

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

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

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

了解更多?预约专属演示

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

企业微信二维码