算法训练营第六天| 206. 反转链表

张开发
• 2026/4/18 8:21:07 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

算法训练营第六天| 206. 反转链表
今日学习的文章链接和视频链接题目链接LeetCode 206. 反转链表视频讲解帮你拿下反转链表 | LeetCode206.反转链表自己看到题目的第一想法看到题目要反转单链表我第一反应是需要改变每个节点的next指针指向。想到可以用双指针法一个指针指向前一个节点一个指针指向当前节点遍历链表时把当前节点的next指向前一个节点。也想到可以用递归递归到链表末尾然后逐层返回反转。自己实现过程中遇到哪些困难双指针法中指针移动顺序容易搞错特别是临时保存next节点的时机。递归法的终止条件没想清楚应该是当前节点为空或者下一个节点为空。反转后新链表的头节点处理不好需要返回最后一个节点。测试时发现空链表和单节点链表需要特殊处理。递归理解有难度特别是递归函数返回的是什么以及如何连接反转后的链表。指针操作容易造成内存访问错误比如访问空指针的next。今日收获心得掌握了双指针反转链表的模板prev、curr、next三个指针配合。理解了递归反转链表的思想先递归到末尾再逐层返回反转。学会了处理链表的边界条件特别是空链表和单节点链表。指针操作要小心顺序一定要先保存next节点再修改curr-next。两种方法的时间复杂度都是O(n)空间复杂度不同迭代O(1)递归O(n)。题目#include iostream using namespace std; 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* prev nullptr; ListNode* curr head; while (curr ! nullptr) { ListNode* next curr-next; curr-next prev; prev curr; curr next; } return prev; } };

更多文章