学做网站网,注册网站代码,设计师网站导航青年帮,胶东网站建设代码随想录二刷 #xff5c; 链表 #xff5c; 翻转链表 题目描述解题思路 代码实现双指针法递归法 206.翻转链表 题目描述
给你单链表的头节点 head #xff0c;请你反转链表#xff0c;并返回反转后的链表。
示例 1#xff1a;
输入#xff1a;head [1,2,3,4… 代码随想录二刷 链表 翻转链表 题目描述解题思路 代码实现双指针法递归法 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
进阶链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题
解题思路 代码实现
双指针法
只需要改变链表的 next 指针的指向直接将链表翻转而不用重新定义一个链表。 首先定义一个 cur 指针指向头节点在定义一个 pre 指针初始化为 null
随后将cur-next节点用 tmp指针保存一下随后将cur - next指向 pre 这样就完成了第一个节点的翻转。
接下来进入循环继续移动 pre 和 cur 指针最后 cur指针指向 null 循环结束链表翻转完成return pre指针 pre指针就指向了头节点。
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* tmp;ListNode* cur head;ListNode* pre NULL;while (cur) {tmp cur - next;cur - next pre;pre cur;cur tmp;}return pre;}
};时间复杂度O(n) 空间复杂度O(1) 递归法
class Solution {
public:ListNode* reverse(ListNode* pre, ListNode* cur) {if (cur NULL) return pre;ListNode* tmp cur - next;cur - next pre;// 递归写法实际上也是做了这两步// pre cur;// cur tmp;return reverse(cur, tmp);}ListNode* reverseList(LKistNode* head) {return reverse(NULL, head);}
};
