206. 反转链表

一、题目描述LeetCode 206. 反转链表给你单链表的头节点head请你反转链表并返回反转后的链表头节点。示例 1输入head [1,2,3,4,5] 输出[5,4,3,2,1]示例 2输入head [1,2] 输出[2,1]示例 3输入head [] 输出[]提示链表中节点的数目范围是 [0, 5000]-5000 ≤ Node.val ≤ 5000二、题目分析反转链表是链表操作中的基础题型也是LeetCode热题100中高频出现的面试考点核心是「改变链表节点的指针指向」将原本“从前到后”的指向改为“从后到前”。核心痛点单链表的节点只有一个next指针一旦直接修改curr-next会丢失后续节点的地址导致遍历中断。因此必须提前保存后续节点的地址再进行指针反转。解题关键使用双指针配合临时指针分别记录“当前节点”“前驱节点”通过循环逐步反转每个节点的指向避免节点丢失效率更高、空间更优。三、解题思路采用「双指针迭代法」无需额外开辟链表空间时间复杂度最优步骤清晰易懂适合新手入门初始化两个指针pre前驱节点初始化为nullptr反转后链表的尾节点指向空curr当前节点初始化为head原链表的头节点循环遍历原链表直到curr为空遍历完所有节点用临时指针tmp保存curr的下一个节点tmp curr-next防止后续修改curr-next后丢失后续节点反转当前节点的指针将curr-next指向pre让当前节点指向它的前一个节点更新双指针pre移动到curr的位置curr移动到之前保存的tmp位置继续遍历下一个节点循环结束后pre会指向原链表的尾节点也就是反转后链表的头节点返回pre即可。补充也可以用递归法解题但递归法空间复杂度为O(n)递归栈消耗不如双指针迭代法O(1)空间最优因此本文重点讲解迭代法适配面试最优解法要求。四、C 代码/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* prenullptr; ListNode* currhead; while(curr){ ListNode* tmpcurr-next; curr-nextpre; precurr; currtmp; } return pre; } };五、代码解析逐行解析代码逻辑新手也能轻松看懂重点标注关键步骤ListNode* pre nullptr;定义前驱节点pre初始化为空因为反转后链表的尾节点原链表头节点的next需要指向空。ListNode* curr head;定义当前节点curr初始化为原链表的头节点从第一个节点开始反转。while(curr)循环条件只要curr不为空就继续反转当curr为空时说明已经遍历完所有节点。ListNode* tmp curr-next;核心步骤临时保存curr的下一个节点因为接下来要修改curr-next的指向不保存会丢失后续节点导致遍历终止。curr-next pre;反转当前节点的指针让curr指向它的前一个节点pre完成当前节点的反转。pre curr;pre指针向前移动一步指向当前已经反转好的节点为下一个节点的反转做准备。curr tmp;curr指针向前移动一步指向之前用tmp保存的下一个节点继续下一轮反转。return pre;循环结束后curr为空pre指向原链表的最后一个节点也就是反转后链表的头节点返回pre即可得到反转后的链表。易错点提醒不要忘记用tmp保存curr-next否则修改curr-next后会找不到后续节点导致代码报错或逻辑错误。六、复杂度分析本题采用双指针迭代法复杂度最优适合面试作答时讲解时间复杂度O(n)其中n是链表的节点个数。循环只遍历一次链表每个节点只被处理一次没有额外的嵌套循环。空间复杂度O(1)只使用了pre、curr、tmp三个指针没有开辟额外的数组、链表等空间属于原地反转空间效率拉满。对比递归法递归法时间复杂度也是O(n)但空间复杂度是O(n)递归调用会占用栈空间栈的深度等于链表长度因此迭代法更优面试中优先推荐使用。七、本题总结这道题是链表操作的入门必刷题也是LeetCode热题100中「链表」模块的基础题型核心考点是「指针反转」和「临时节点保存」。重点掌握双指针迭代法的思路核心是用pre记录前驱节点curr遍历当前节点tmp保存后续节点三步完成一次指针反转循环迭代即可完成整个链表的反转。面试提醒这道题常出现在初面的算法题中面试官可能会要求手写代码并且追问“如何优化空间复杂度”“递归法如何实现”建议同时掌握迭代法和递归法应对追问。拓展本题的变形题如反转链表的前k个节点、反转链表的中间部分核心思路都和本题一致都是基于双指针的指针反转掌握本题后后续变形题可轻松应对。