LeetCode 206. 反转链表 双指针法 辅助结点 递归
2021/11/16 23:16:16
本文主要是介绍LeetCode 206. 反转链表 双指针法 辅助结点 递归,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
提示:
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?
双指针法+辅助结点:
AC代码
/** * 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* pre = nullptr; //也可以理解为前哨结点 ListNode* cur = head; //此时pre 与 cur就构成了一对待处理的结点 ListNode* tmp; //辅助结点 用处保留下一个待处理的结点 while(cur!=nullptr){ tmp = cur->next; cur->next = pre; //下一对要处理的结点 pre = cur; cur = tmp; } return pre; } };
递归解法,思路本质上与上面的是相同的:
AC代码
class Solution { public: ListNode* reverse(ListNode* pre, ListNode* cur){ if(cur == nullptr) return pre; ListNode* tmp = cur->next; cur -> next = pre; //更新 //pre = cur; //cur = tmp; return reverse(cur, tmp); } ListNode* reverseList(ListNode* head) { return reverse(nullptr, head); } };
这篇关于LeetCode 206. 反转链表 双指针法 辅助结点 递归的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升