网站网页制作的公司,沈阳网站推广优化,idc销售网站php源码,广州市官网网站建设多少钱题目链接#xff1a;206. 反转链表
题目描述
给你单链表的头节点 head #xff0c;请你反转链表#xff0c;并返回反转后的链表。
示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5] 输出#xff1a;[5,4,3,2,1] 示例 2#xff1a; 输入#xff1a;head [1,2] 输…题目链接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 文章讲解代码随想录
视频讲解帮你拿下反转链表 | LeetCode206.反转链表 | 双指针法 | 递归法_哔哩哔哩_bilibili
题解1双指针
思路一个指针指向当前节点另一个指针指向上一个节点用一个变量存储下个节点的位置遍历链表的过程中反转链表。
/*** Definition for singly-linked list.* function ListNode(val, next) {* this.val (valundefined ? 0 : val)* this.next (nextundefined ? null : next)* }*/
/*** param {ListNode} head* return {ListNode}*/
var reverseList function(head) {let pre null, cur head; // cur 指向当前节点pre 指向上一个节点while (cur) {const temp cur.next; // 临时存储下个节点位置cur.next pre; // 反转当前节点pre cur; // 更新 precur temp; // 更新 cur}return pre; // pre 即为反转后链表的头节点
};
分析遍历一次链表时间复杂度为 O(n)空间复杂度为 O(1)。
题解2双指针递归
思路使用双指针法的思路从左到右一边遍历一边反转链表。反转当前节点和上一个节点再递归的反转下一个节点。
递归解析
函数功能传入上一个节点和当前节点反转整个链表。结束条件当前节点指向 null即已反转整个链表。递归关系反转当前节点和上一个节点继续递归的反转当前节点和下一个节点即可反转整个链表。
/*** Definition for singly-linked list.* function ListNode(val, next) {* this.val (valundefined ? 0 : val)* this.next (nextundefined ? null : next)* }*/
/*** param {ListNode} head* return {ListNode}*/
var reverseList function(head) {const reverse function(pre, cur) {// cur 指向当前节点pre 指向上一个节点// cur 为空时递归结束返回 pre 为头节点if (cur null) {return pre;}// cur 不为空时执行反转操作const temp cur.next; // 临时存储下个节点位置cur.next pre; // 反转当前节点return reverse(cur, temp); // 执行函数反转链表的剩余部分};return reverse(null, head);
};
分析递归的遍历了一次整个链表同时调用了 n 层栈空间时间复杂度为 O(n)空间复杂度为 O(n)。
题解3暴力递归
思路当链表为空链表或只有1个元素时反转后的链表即为它本身。链表元素大于1个时需要反转第1个元素和剩余部分反转后的链表的最后一个元素即反转前链表的第2个元素。
递归解析
函数功能传入链表头节点返回反转后的链表。结束条件链表为空链表或只有1个元素返回这个链表的头节点。递归关系反转一个链表先反转第2个节点即之后的部分即除头节点外的部分再反转头节点和剩余部分链表反转后的尾节点即第2个节点即可完成链表反转。
/*** Definition for singly-linked list.* function ListNode(val, next) {* this.val (valundefined ? 0 : val)* this.next (nextundefined ? null : next)* }*/
/*** param {ListNode} head* return {ListNode}*/
var reverseList function(head) {// 如果链表为空链表即 head 指向 null或只有一个元素返回 headif (head null || head.next null) {return head;}// 递归反转第1个节点后的剩余链表const start reverseList(head.next); // start 为反转后的链表的头节点// 反转第1个节点和第2个节点第2个节点即反转后的链表的尾节点head.next.next head;head.next null;return start;
};
分析递归的遍历了一次整个链表同时调用了 n 层栈空间时间复杂度为 O(n)空间复杂度为 O(n)。
收获
1. 学会了反转链表的多种方法本质上是用双指针的思想用两个指针分别指向当前元素和上一个元素再使用临时变量存储下一个元素的位置。
2. 学会了使用递归的思想解决问题题解2和题解3都是使用的递归的思想。区别在于题解2的思路是在正向的遍历链表的过程中同时反转链表而题解3的思路是先遍历到链表尾遍历途中在递归栈中存储每个节点的信息再从链表尾部开始向头部反转链表。
