教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载反转单链表是 LeetCode 上最经典的链表基础题之一也是计算机校招、社招笔试面试中出现频率极高的手写代码题。本文以 InterviewGuide 仓库中精选力扣 300 题目之链表分区的 206. 反转链表 为核心完整继承原文档的题目与解法并结合仓库中剑指 Offer 题解、面试高频算法真题中的多种实现变体从指针细节、边界条件、复杂度三个维度把这道题讲透。读完本文你将能够徒手写出迭代、头插、递归三种解法并理解它们各自的适用场景与面试考察点。一、题目理解与考点分析题目描述反转一个单链表。示例输入: 1-2-3-4-5-NULL 输出: 5-4-3-2-1-NULL进阶要求原文档原文你可以迭代或递归地反转链表。你能否用两种方法解决这道题这道题表面只考指针翻转实际考察的是三个层面的基本功链表指针操作的正确性能否在不丢失后继节点引用的情况下完成指针重连边界情况的完备性空链表、只有一个节点的链表、两个节点的链表是否都能正确处理多解法能力进阶要求明确提示迭代或递归面试官通常希望候选人能说出两种及以上的实现并对比时间/空间复杂度。仓库中的链表分区目录将链表 Easy 题归纳为三道——21. 合并两个有序链表、206. 反转链表、237. 删除链表中的节点其中 206 是纯粹考察指针重连基本功的题目适合作为链表专项的入门第一题反复练习。二、解法一三指针迭代法原文档第一版原文档给出的第一版解法是典型的三指针迭代法也是竞赛与面试中最推荐的手写实现。原文如下完整保留struct ListNode { int val; ListNode* next; ListNode(int x) :val(x), next(nullptr) {} }; ListNode* reverseList(ListNode* head) { ListNode* pre nullptr; ListNode* curr head; ListNode* next nullptr; while (curr) { next curr-next; curr-next pre; pre curr; curr next; } return pre; }原文档记录了作者当年在 LeetCode 上以 C 提交的历史数据执行用时 12 ms在所有 cpp 提交中击败 78.92% 的用户内存消耗 9.2 MB击败 20.28% 的用户注这是文档撰写时的历史评测数据不同时期的评测环境不同参考价值在于该实现属于第一梯队的时间表现。2.1 三个指针各司其职理解这段代码的关键是搞清楚pre、curr、next三个指针在每一轮循环中的职责指针初始值职责prenullptr已反转部分的头节点即当前节点的前驱currhead当前待反转的节点nextnullptr保存curr原本的后继防止断链后丢失循环体内共四步顺序不能乱next curr-next先保存后继节点这是整个算法不出错的前提——一旦执行第 2 步原后继就再也找不回来了curr-next pre将当前节点的指针反向指向它的前驱pre curr当前节点成为已反转部分的新头部curr next移动到原链表的下一个节点继续处理。2.2 手动走一遍1 - 2 - 3 - 4 - 5 - NULL以输入链表为例逐步推演指针状态轮次进入循环前curr指向操作后pre指向curr更新为链表形态已反转部分1节点 1节点 1节点 21 - NULL2节点 2节点 2节点 32 - 1 - NULL3节点 3节点 3节点 43 - 2 - 1 - NULL4节点 4节点 4节点 54 - 3 - 2 - 1 - NULL5节点 5节点 5nullptr5 - 4 - 3 - 2 - 1 - NULL循环终止条件是curr为nullptr遍历完原链表此时pre恰好停在原链表的尾节点上也就是反转后新链表的头节点直接return pre即可。2.3 边界条件自查空链表head nullptr循环体一次都不执行返回pre即nullptr正确单节点链表第一轮循环将curr-next置为prenullptr返回该节点自身正确两节点链表两轮循环即可完成反转next在第 2 轮保存的是nullptr同样安全。可以看到三指针法天然对空链表和单节点链表免疫无需额外的判空分支这也是它被广泛采用的重要原因。时间复杂度和空间复杂度分别为O(n) 与 O(1)。三、解法二头插法剑指 Offer 经典做法仓库的剑指 Offer 题解 No15. 反转链表 与面试高频算法真题 中均收录了另一种经典思路——头插法。其核心思想是借助一个虚拟头节点dummyNode把原链表中的节点依次摘下并头插到虚拟头之后遍历结束后dummyNode-next就是反转后的新链表头。仓库中给出的实现如下ListNode* ReverseList(ListNode* pHead) { // 头插法 if (pHead nullptr || pHead-next nullptr) return pHead; ListNode dummyNode ListNode(0); ListNode* pre (dummyNode); pre-next pHead; ListNode* cur pHead-next; pHead-next nullptr; //pre cur; ListNode* temp nullptr; while (cur ! nullptr) { temp cur; cur cur-next; temp-next pre-next; pre-next temp; } return dummyNode.next; }3.1 头插法为什么稳注意到这里的关键细节ListNode dummyNode ListNode(0);将虚拟头节点直接开辟在栈上而不是用malloc/new动态分配。仓库中的原注释写得很直白——头插法来做将元素开辟在栈上这样会避免内存泄露。在面试手写代码时栈上对象自动析构、无需手动释放可以省去很多内存管理的麻烦。算法流程分解判空链表为空或只有一个节点时直接返回pHead创建栈上虚拟头节点dummyNode令pre dummyNodepre-next pHead先把pHead-next置空即原链表第一个节点直接成为反转后的尾节点从pHead-next即cur开始遍历每轮摘下cur执行temp-next pre-next; pre-next temp;把它插到虚拟头节点之后循环结束后dummyNode.next即为新链表头。每一步头插虚拟头节点之后都多出一个最新摘下的节点最终节点的顺序正好与原链表完全相反天然完成了反转。该解法的时间复杂度同样为O(n)、空间复杂度O(1)只额外使用一个栈上的虚拟头节点。仓库中剑指 Offer 题解还记录了二刷时的评测数据头插法运行时间 3 ms、占用内存 364k三指针迭代法运行时间 3 ms、占用内存 504k同样为当时的本地/在线评测历史数据仅作参考。四、解法三递归法响应进阶要求原文档的进阶要求明确提示你可以迭代或递归地反转链表这里补充递归实现及其原理方便读者完整覆盖两种思路。ListNode* reverseList(ListNode* head) { // 递归出口空链表或单节点链表无需反转 if (head nullptr || head-next nullptr) { return head; } // 先反转 head 之后的子链表newHead 是反转后的新头 ListNode* newHead reverseList(head-next); // 让当前节点的后继原 head-next反过来指向当前节点 head-next-next head; // 断开当前节点原来的正向链接避免成环 head-next nullptr; return newHead; }递归解法在面试中考察的是对递归不变量的理解先递后归假设reverseList(head-next)已经正确返回了从head-next到链表末尾这一段反转后的新头节点newHead回溯时重连回到当前层后head-next此时是这段子链表反转后的尾节点也就是原来的head-next节点执行head-next-next head把它指向head收尾防环head-next nullptr切断head原本指向后继的边否则两个节点会互相指向形成环逐层返回每一层都返回同一个newHead也就是原链表尾节点反转后它成为新链表头。与迭代法相比递归的时间复杂度同样是O(n)但空间复杂度为O(n)递归栈深度与链表长度成正比。因此链表较短时递归写法更简洁、可读性好链表很长时递归存在栈溢出风险迭代法三指针更稳妥。面试时建议先给出迭代实现再补充递归实现并主动对比两者空间复杂度差异这通常是这道题的加分点。五、仓库中的完整可运行测试程序在面试高频算法真题中仓库还提供了一段完整的、可本地编译运行的测试程序包含链表构建、反转与遍历输出三个部分适合用来在本地验证上面任意一种解法#includealgorithm #includeunordered_map #include iostream #includevector using namespace std; struct node { int data; struct node* next; node(int _data) :data(_data), next(nullptr) { } }; struct node* init() { node* head new node(1); node* node1 new node(2); node* node2 new node(3); node* node3 new node(4); node* node4 new node(5); head-next node1; node1-next node2; node2-next node3; node3-next node4; node4-next nullptr; return head; } struct node* reverse(node* head) { struct node* pre new node(-1); struct node* temp new node(-1); pre head; temp head-next; pre-next nullptr; struct node* cur new node(-1); cur temp; while (cur ! nullptr) { temp cur; cur cur-next; temp-next pre; pre temp; } return pre; } int main(){ auto head init(); head reverse(head); while (head ! nullptr) { cout head-data endl; head head-next; } return 0; }这段代码的init()负责构造1 - 2 - 3 - 4 - 5的五节点链表reverse()用先断开头节点、再逐个前插的思路完成反转main()输出反转后的链表。编译运行后终端会依次打印5 4 3 2 1与 LeetCode 示例的期望输出完全一致。读者可以用它作为最小验证工程把上文的三指针、头插、递归三种实现分别替换进reverse()中做对照测试。六、三种解法对比与面试要点解法核心思路时间复杂度空间复杂度是否修改原链表适用场景三指针迭代就地翻转每条next指针O(n)O(1)是面试首选无栈溢出风险头插法dummy node借虚拟头节点依次头插O(n)O(1)是剑指 Offer 经典考法代码稳递归先反转子链表再回溯重连O(n)O(n)是展示递归功底短链表友好面试中围绕这道题的高频追问包括为什么next curr-next必须放在循环第一步——因为第二步curr-next pre会覆盖curr的原后继必须先保存否则链表断开后无法继续遍历反转后如何找到新头——迭代结束时pre停在原链表尾节点头插法结束时dummyNode.next即新头递归结束时newHead即新头空间复杂度能优化吗——递归可改写为尾递归/迭代以将空间降到 O(1)但注意普通递归的调用栈深度与链表长度成正比超长链表需谨慎能否做到只反转部分区间如 m 到 n——这是 206 的进阶变体力扣 92 题核心思路是在三指针迭代的基础上记录区间前驱与区间后继。七、延伸阅读与仓库导航链表分区目录Easy 级共三道链表题206 反转链表之外还有21. 合并两个有序链表两个有序链表拼接成一个有序链表考察双指针归并237. 删除链表中的节点只给节点不给头指针用值替换完成删除剑指 Offer No15. 反转链表同一考点的牛客版题目输入{1,2,3}输出{3,2,1}含头插法、三节点更替、二刷优化共四个版本代码面试高频算法真题收录了反转链表的完整可运行测试程序及其他高频手写题精选力扣 300 道算法题专栏介绍了解该专栏的 13 大标签分类与刷题思路Easy 级链表题汇总页三题合并的集中排版版本。建议的练习路径是先闭卷写出三指针迭代法 → 再默写头插法 → 最后尝试递归法并口述其回溯过程三者都能在 3 分钟内完成时这道题才算真正过关。反转链表也是后续环形链表、K 个一组翻转链表、回文链表等复杂题目的基础值得投入时间把它练成肌肉记忆。赞分享教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载相关推荐LeetCode 206.反转链表阿秀 InterviewGuide 链表专题迭代与递归双解法实战解析LeetCode 206.反转链表阿秀 InterviewGuide 链表专题迭代与递归双解法实战解析 本文基于 InterviewGuide 仓库《精选力扣文档教程知识库剑指Offer No15 反转链表头插法、三指针迭代与递归的完整解法剖析InterviewGuide 校招刷题笔记剑指Offer No15 反转链表头插法、三指针迭代与递归的完整解法剖析InterviewGuide 校招刷题笔记 本文基于 InterviewGuide教程剑指Offer No15 反转链表头插法与三指针迭代的四种 C 解法——InterviewGuide 刷题笔记剑指Offer No15 反转链表头插法与三指针迭代的四种 C 解法——InterviewGuide 刷题笔记 导读本文以 InterviewGuide文档教程知识库创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考