吴中区网站建设技术,做编程的 网站,泰安房产网签住宅,怎样如何做网站赚钱206. 反转链表
题目#xff1a;
给你单链表的头节点 head #xff0c;请你反转链表#xff0c;并返回反转后的链表。
示例#xff1a;
示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5]
输出#xff1a;[5,4,3,2,1]示例 2#xff1a; 输入#xff1a;head [1…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
**进阶**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题
解题
方法一迭代 之前链表的头节点是元素 1 反转之后头结点就是元素 5 这里并没有添加或者删除节点仅仅是改变 next 指针的方向。
思路是
首先定义一个 cur 指针指向头结点再定义一个 pre 指针初始化为 null。
然后就要开始反转了首先要把 cur-next 节点用 tmp 指针保存一下也就是保存一下这个节点。
为什么要保存一下这个节点呢因为接下来要改变 cur-next 的指向了将cur-next 指向 pre 此时已经反转了第一个节点了。
接下来就是循环走如下代码逻辑了继续移动 pre 和 cur 指针。
最后cur 指针已经指向了 null循环结束链表也反转完毕了。 此时我们 return pre 指针就可以了pre 指针就指向了新的头结点。
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* temp; // 保存cur的下一个节点ListNode* cur head;ListNode* pre NULL;while(cur) {temp cur-next; // 保存一下 cur的下一个节点因为接下来要改变cur-nextcur-next pre; // 翻转操作// 更新pre 和 cur指针pre cur;cur temp;}return pre;}
};复杂度分析
时间复杂度O(n)其中 n 是链表的长度。需要遍历链表一次。空间复杂度O(1)。
方法二递归
看官方解答吧这里只贴一下解题代码
206. 反转链表 - 力扣LeetCode
class Solution {
public:ListNode* reverseList(ListNode* head) {if (!head || !head-next) {return head;}ListNode* newHead reverseList(head-next);head-next-next head;head-next nullptr;return newHead;}
};复杂度分析 时间复杂度O(n)其中 n 是链表的长度。需要对链表的每个节点进行反转操作。 空间复杂度O(n)其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间最多为 n 层。
度分析** 时间复杂度O(n)其中 n 是链表的长度。需要对链表的每个节点进行反转操作。 空间复杂度O(n)其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间最多为 n 层。
