天水市建设局网站公告,番禺网站制作费用,蒙古网站后缀,郑州seo优化哪家好首先需要了解链表的概念
先把 next 记录下来
无论是插入#xff0c;删除#xff0c;还是翻转等等操作#xff0c;先把 next 指针用临时变量保存起来#xff0c;这可以解决 90% 重组链表中指向出错的问题#xff0c;
如果不知道什么时候需要用到守卫#xff0c;那就都用…首先需要了解链表的概念
先把 next 记录下来
无论是插入删除还是翻转等等操作先把 next 指针用临时变量保存起来这可以解决 90% 重组链表中指向出错的问题
如果不知道什么时候需要用到守卫那就都用
类型守卫 emptyNode 是创建的一个空的节点并将它连接到 head 节点之前无论链表进行任何操作 emptyNode 都指向最后的头节点是一个很实用的小方法如果不知道什么时候用什么时候不用那就先都用起来吧
其实在大部分时候emptyNode 都是能用上即便只是遍历查找值用上作为第 0 个值当要找第 k 个值的时候也不需要再判空处理啊
头节点判空处理
如果懒或者经常忘记看题目的给定条件头节点判空都做起来对于一些翻转题还得将 head.next 也判断起来
到熟练之后其实可以不做但是用上最多就浪费一段代码也还好
画图画图画图
遇事不决的时候还是要画图一步一步的连起来总能够捋清楚的画图是链表的关键所在
链表的节点是保存在内存中的一个数据结构
链表是一个特定的数据结构在 JS 中可以表现为一个拥有 val 和 next 属性的对象所以遇到形如交换两个链表节点的时候千万不能交换两个链表的 val 值虽然 LC 有一些题是可以过但是实际上是不合理的而且一旦出现这种思想对于一些经典题 160. 相交链表 就会理解不了
记住链表是一个数据结构不是一个值可以类比成一个对象交换链表比如不是简单交换值
都是中等题
这里选的都是按照 LC 火热排序中等难度的题感觉纯链表学习做特别难没太大必要毕竟我只是一个菜鸟大佬们可以自由选择一起 进大厂
具体题解
剑指 Offer 24. 反转链表
分析
注意保护好下一个节点 next然后不断维护上一个节点和当前阶段不断往后推即可
var reverseList function (head) {let prev null;while (head) {const next head.next;head.next prev;prev head;head next;}return prev;
};
面试题 02.05. 链表求和
分析
这题是头对齐445. 两数相加 II 是尾对齐对于头对齐而已链表比较容易进行进位后直接构建成链表。当两个链表都存在的时候共有三个值需要相加分别是 l1.val l2.val isUpper当其中一个链表走完了就只剩下一个链表和 isUpper, 需要注意的是我们不知道哪个链表更长所以需要判断一下链表遍历完了还要判断一下 isUpper 是否还有还有就得再进一个节点反转的数据结构就是 O(nm)
/** * 分析 * 1. 这里的返回值是按照十进制计算后的 链表 */
var addTwoNumbers function (l1, l2) {const emptyNode new ListNode();let current emptyNode;let isUpper 0; // 是否满10为后面的位1while (l1 l2) {let sum l1.val l2.val isUpper;if (sum 10) {isUpper 1;sum sum % 10;} else {isUpper 0;}current.next new ListNode(sum);current current.next;l1 l1.next;l2 l2.next;}let l3 l1 || l2; //剩余的那个链表while (l3) {let sum l3.val isUpper;if (sum 10) {isUpper 1;sum sum % 10;} else {isUpper 0;}current.next new ListNode(sum);current current.next;l3 l3.next;}if (isUpper) {// 遍历完了如果还有进位current.next new ListNode(isUpper);current current.next;}return emptyNode.next;
};
445. 两数相加 II
分析
这题是尾对齐面试题 02.05. 链表求和 是头对齐对于头对齐而已链表比较容易进行进位后直接构建成链表。所以这题先把两个链表反转然后用面试题 02.05. 链表求和 方式组合完再反转回去即可当然我们可以用数组或其他额外的数据结构来保存两数之和最后再统一处理但是因为是链表专题所以除了不用额外的数据结构处理反转的数据结构就是 O(nm)
var addTwoNumbers function (l1, l2) {const emptyNode (current new ListNode());// 翻转量个链表让他们头节点对齐let temp1 reverseList(l1);let temp2 reverseList(l2);let isUpper 0; // 是否满10为后面的位1while (temp1 temp2) {let sum temp1.val temp2.val isUpper;if (sum 10) {isUpper 1;sum sum % 10;} else {isUpper 0;}current.next new ListNode(sum);current current.next;temp1 temp1.next;temp2 temp2.next;}let l3 temp1 || temp2; //剩余的那个链表while (l3) {let sum l3.val isUpper;if (sum 10) {isUpper 1;sum sum % 10;} else {isUpper 0;}current.next new ListNode(sum);current current.next;l3 l3.next;}if (isUpper) {// 遍历完了如果还有进位current.next new ListNode(isUpper);current current.next;}return reverseList(emptyNode.next);
};// 反转链表
var reverseList function (head) {let prev null;while (head) {const next head.next;head.next prev;prev head;head next;}return prev;
};
参考视频传送门
61. 旋转链表
分析
从链表尾部阶段 k 长度拼在前面即可 – 其中 k (K %len) 如果移动了 len 的位置就又回到了原来的位置了需要注意的是一些边界条件但是这里直接定义 prev 为安全守卫一切需要保存或者拼接的节点都应用 prev 来处理就可以避免 cur 为 null 的时候无法获取 next 指针的尴尬因为 cur 是实际走的指针prev 只是一个安全守卫它始终是存在的。时间复杂度O(N)
var rotateRight function (head, k) {// 先求链表的长度let len 0,tempNode head;while (tempNode) {len;tempNode tempNode.next;}// 需要位移 size 到头节点let size len - (k % len);let prev new ListNode();prev.next head;let cur head;while (size--) {cur cur.next;prev prev.next;}//保存移动之后的尾部节点let tail prev;// 继续往前走while (cur) {cur cur.next;prev prev.next;}// 原来的尾结点和头节点相连prev.next head;// 获取移动后的头节点const next tail.next;// 尾结点的 next 指针指向的是 nulltail.next null;return next;
};
82. 删除排序链表中的重复元素 II
分析
删除已经排好序的链表的重复节点最后返回一个新的链表需要注意的是这里是删除所有重复的节点而不是保留一个值即 1-2-2-3 将重复的 2 节点全部删除得到 1-3所以在遍历 head 的时候需要分两种情况一个是 head 的下一个节点有值且与 head 的值相等时head 自己往下走知道 head.next null 或者 head.next.val ! head.val 为止如果是删除节点后本次遍历需要重新整理 prev 节点和 head 节点如果是普通遍历则正常走即可时间复杂度:O(N)
var deleteDuplicates function (head) {let emptyNode (prev new ListNode());emptyNode.next head;while (head) {while (head.next head.val head.next.val) {head head.next;}if (prev.next ! head head.val prev.next.val) {// 这是遇到重复值时删除节点后进行整理 prev.next 重新指向新的 head 节点head head.next;// 重新连接起来prev.next head;} else {// 这是正常没有重复值走prev prev.next;head head.next;}}return emptyNode.next;
};
86. 分隔链表
分析
遍历链表找出值大于等于 x 的第一个节点 K然这个时候前面那些节点都不用动了因为都是小于 x 的然后从 K 开始找出小于 x 的节点移动到 K-1 - K 之间的位置即可由于存在插入和删除操作所以需要用到 prev 指针和 cur 指针由于可能存在第一个节点就是大于等于 x 的 K 所以需要安全守卫 emptyNode时间复杂度 O(N) 注意面试题 02.04. 分割链表 这道题和本题类似但是不保留每个分区的初始相对位置 var partition function (head, x) {let emptyNode (prev new ListNode());emptyNode.next head;while (head head.val x) {head head.next;prev prev.next;}// 走完了或者遇到了 K,保存一下这个前置节点let tail prev;// 这个时候找到小于 x 的就要处理了while (head) {if (head.val x) {const next head.next;// 插入到 tail 和 tail.next 之间head.next tail.next;tail.next head;tail tail.next;// 删除 head 节点,重新设置新的 headprev.next next;head next;} else {head head.next;prev prev.next;}}return emptyNode.next;
};
109. 有序链表转换二叉搜索树
分析
这里说的高度平衡说人话其实就是尽可能平均的将节点分配到左右子树中那么找出中间节点然后平分到左右节点树就是比较合适的解这种设置节点然后最后成树的操作使用自底向上的思路就很合适不断二分切割链表知道只有一个节点的时候就作为叶子节点然后返回去这里使用快慢指针找到中间节点 slow 注意这个节点是向上取中点的所以就是当前节点的值然后将前面一段链表分给左树右边一段链表分给右树这里用到了 BST 中左树节点永远小于根节点小于右侧节点的特性以及本轮链表就是单增链表的特性时间复杂度 O(N) 还是相当于遍历一个完整的链表
var sortedListToBST function (head) {const recursion (head) {if (!head) return null; // 空节点// 使用双指针找出中间节点 -- 这是向上取整let emptyNode (prev new ListNode());prev.next head;let slow (fast head);while (fast fast.next) {slow slow.next;fast fast.next.next;prev prev.next;}// 以 slow 为根节点左侧一段离岸边要截断prev.next null;const node new TreeNode(slow.val);node.left recursion(emptyNode.next);node.right recursion(slow.next);return node;};return recursion(head);
};
142. 环形链表 II
分析
相比于 141. 环形链表 不但要判断是否有环还得算出入环的那个节点这里进行的一系列计算都必须保证起点是一样的这样才能保证走出来的路径长度是适合的。画图可得将起始点到环起点记作 l , 环长 r, 快慢指针相交的点距离环起点为 s, 由于快指针是慢指针速度的 2 倍,根据速度一定可以得到等式 s (n-2m)r-l 其中 n,m 是快慢指针走的环的圈数量这两个变量不重要只需要表示他们分别走了 n, m 圈后相交了这个时候我们发现如果原来的慢指针继续走到环节点需要走的路程是 (r-s) (1-n2m)rl ;这个时候我们在起始点重新开启一个新的慢节点 newSlow, 让他们一起走一段路 l, 他们切好在起点相遇时间复杂度 O(N)
var detectCycle function (head) {if (!head) return null; //一个节点都没得还有啥环const emptyNode new ListNode();emptyNode.next head;let slow (fast emptyNode); // 相当于走了走了一次了while (fast fast.next) {// 一开始都是从边界守卫开始这样可以防止在第一个节点就有环了slow slow.next;fast fast.next.next;if (slow fast) {// 在环中的某一个点相交了let newSlow emptyNode;while (slow ! newSlow) {newSlow newSlow.next;slow slow.next;}return newSlow;}}return null; //如果会跳出来证明无环
};
147. 对链表进行插入排序
分析
编辑读写指针write 指针前是排好序的链表即它的是前面链表的最大值read 指针遇到比 write 指针值大于等于的节点则 write 指针跟着移动遇到小于 read 的指针删除节点并在 write 指针前找到一个合适的位置插入时间复杂度 O(nlogn)
var insertionSortList function (head) {if (!head || !head.next) return head;let emptyNode new ListNode();emptyNode.next head;let write head,read head.next;while (read) {if (read.val write.val) {// 读指针比写指针更大的时候一起走read read.next;write write.next;} else {// 删除 read 指针然后从 emptyNode 到 write 中找个位置插入// 先删除 -- 这个时候 read 指针先当做一个普通节点使用,注意: write 指针其实一直都在 read 之后和 prev 指针的作用差不多write.next read.next;let em emptyNode;while (em.next.val read.val) {em em.next;}// 插入 em.next read.val , 所有插入到 em - read - em.nextread.next em.next;em.next read;// 把 read 指针放回到 write 之后再继续走 -- 这里当然可以用临时遍历处理但是read write.next;}}return emptyNode.next;
};
328. 奇偶链表
分析
这里的奇偶性是排序奇偶性类比数组的下标的奇偶性而并非是值的奇偶性原地转移且要保持奇偶节点的相对顺序也就是不能直接将奇偶节点交换位置只能插入 1-2-3-4-5 只能是 1-3-5-2-4 而不能是 1-3-5-4-2仍然使用快慢指针快指针从初始位置启动每次走 2 步也就是说 fast 指针指向奇数节点slow 指针指向匹配好全奇的尾结点每次将 fast 节点删除然后插入到 slow 节点之后由于整体长度是不变的所以 fast 节点删除后要保持在奇数位置就得设在临时的 prev 节点上
var oddEvenList function (head) {if (!head || !head.next) return head; // 两个节点都没得直接回家吧let emptyNode new ListNode();emptyNode.next head;let fast (slow head);while (fast fast.next) {// 这是fast的前一个节点用来删除 fast 节点 -- 同时作为在前面插入删除节点后重新锚点的位置const prev fast.next;fast fast.next.next;if (fast) {// 删除 fast 节点prev.next fast.next;fast.next slow.next;slow.next fast;slow slow.next;// 恢复 fastfast prev;}}return emptyNode.next;
};
160. 相交链表
分析
长度不一样的链表肯定不会在起始节点就相交这是必然所谓相交链表就是这个子链表是完全一样的可以假设有 a,b,c 三个链表然后 a,b 的尾结点同时指向 c, 即 aTail.next c , bTail.next c 这个时候形成的新的链表 headA 和 headB 的相交链表就是 c需要注意的是 aTail 和 bTail 可能会存在值相等但是实际缺不是一个节点的情况但是在 LC 的链表序列化中以数组的形式存在就会迷惑为什么不是在 aTail 这个节点就是相交节点需要特别注意所以我们一起走两个链表直到其中一个结束找出可能剩下没走完的那个链表就可以判断除 long 长链表和 short 短链表, 以及剩余未走的链表 tempC如何让 long 和 tempC 一起走完这个时候 long 和 short 长度就一致了可以开始判断相交性
var getIntersectionNode function (headA, headB) {let tempA headA,tempB headB;while (tempA tempB) {// 一起走tempA tempA.next;tempB tempB.next;}// tempC 是剩下的 long 是更长的链表if (tempA) {tempC tempA;long headA;short headB;} else {tempC headB;long headB;short headA;}// 将 long 多出来的节点先走完得到和 short 相同长度的链表while (long) {while (tempC) {tempC tempC.next;long long.next;}}while (long) {if (long short) return long;long long.next;short short.next;}return null;
};
分析 – 压缩一下
原理基本是一致的都是用临时变量分辨走 headA 和 headB 然后判断是否存在相同的点如果最后走完了还没有则返回 null – 目标就是实现两个长度相等的链表再比较如果 headA 和 headB 长度一致那么一开始就遍历两个链表并找出是否相交如果相交则跳出循环返回相交节点如果没有相交节点则一起走到 null也跳出循环返回 null如果 headA 和 headB 长度不一致,那么就先一起遍历结束短链表变量 A 切换到长链表 long继续和剩下的原长链表多出的表走直到长链表变量 B 切换到短链表 short此时变量 A,B 对应的链表长度已经相等继续遍历然后进行步骤 2 的判断时间复杂度 O(nm)
var getIntersectionNode function (headA, headB) {let tempA headA,tempB headB;while (tempA ! tempB) {tempA tempA ? tempA.next : headB;tempB tempB ? tempB.next : headA;}return tempA;
};
1721. 交换链表中的节点
分析
先用双指针求出正序第 k 个节点 first 和反序第 k 个节点 second现在要交换 first 和 second 需要先判断他们两个节点是不是相邻相邻节点可以直接处理如果不是相邻节点那么就用删除插入的方法将两个节点进行交换注意: 当 first 和 second 求到之后直接将里面的 val 值修改在 leetcode 上是可以走通的但是这其实是不符合题意的这就和相交链表 中的迷惑一样为什么 a2 节点值明明一样但是相交节点缺是 a3 是一样的交换了值但是节点在存储位置是不变的所以真是节点并没有改变这算是 LC 在这题中 边界设计有问题吧对于 JS 来说我们一般可以用对象来模拟链表的节点从这个方面看每个节点都是单独的对象里面有一个属性 val我们声明了两个对象val 是一样的但是他们却是不同的对象因为他们在内存中存储的位置是完全不一样的。
var swapNodes function (head, k) {if (!head) return head;let emptyNode new ListNode();emptyNode.next head;let pFirst emptyNode;let first head;while (--k) {first first.next;pFirst pFirst.next;}// 现在 first 就是正向第 k 个节点,只需要保存let temp first.next;let pSecond emptyNode;let second head;while (temp) {temp temp.next;pSecond pSecond.next;second second.next;}// 这个时候 second 就是反向第 K 个节点if (first.next second) {// 相邻节点交换pFirst.next second;first.next second.next;second.next first;} else if (second.next first) {// 相邻节点交换pSecond.next first;second.next first.next;first.next second;} else {// 交换 first 和 secondconst fNext first.next;const sNext second.next;pFirst.next second;pSecond.next first;second.next fNext;first.next sNext;}return emptyNode.next;
};
725. 分隔链表
分析
两个关键点每一个部分尽可能平均前面的链表长度大于后面的链表长度直接计算出链表长度取除数可以得到最短长度 n取余可以知道前面 m 个链表的长度要为 n1再一次遍历链表使用读写指针分割好保存到数组中
var splitListToParts function (head, k) {if (!head) return new Array(k).fill(null); // 没有节点也要切只是切成 k 份的 nulllet emptyNode new ListNode();emptyNode.next head;let temp head;let len 0;while (temp) {len;temp temp.next;}const n Math.floor(len / k);let m len % k; // 前 m 个链表取 n1 个值let write (read head);let ret [];let other k - m;// 插入 m 个 n1 的链表while (m--) {let count 0;//前 m 个值,最少都还有一个值while (count n) {read read.next;count;}// 此时 read 指针在切割指针的位置const next read.next;read.next null; //切割ret.push(write);write next;read next;}// 再插入 k-m 个 n 长度的链表while (other--) {if (n 0) {ret.push(null);} else {let count 0;while (count n - 1) {read read.next;count;}// 此时 read 指针在切割指针的位置const next read.next;read.next null; //切割ret.push(write);write next;read next;}}return ret;
};
817. 链表组件
分析
这里说明了 head 中的值都是唯一的且 nums 中的值都是 haed 值中的子集所以可以另开一个 [0,N-1] 的数组将 nums 的值作为下标放进去这样就可以直接用数组下标判断 head 中的值是否包含在 nums 中且复杂度为 O(1)最后返回值是有多少个组件也就是一旦断开链表组件数量就加一时间复杂度 O(N) ; 空间复杂度 O(N)
var numComponents function (head, nums) {const arr [];for (let num of nums) {arr[num] 1;}let len nums.length;let ret 0;let count 0; //每一个组件的长度 -- 必须大于 1 才能组成一个组件while (head len) {if (arr[head.val]) {// nums 的值在减少一旦为 0 了就结束遍历了count; // 万一需要求最大组件就可以用这个 count 了len--;}if (count !arr[head.val]) {// 处于匹配状态但是这一次却没有匹配值ret;count 0; // 恢复到 0, 继续下一次的匹配}head head.next;}return count ? ret 1 : ret; //弹出遍历时如果还存在有匹配的组件没计算则再加1
};
707. 设计链表
分析
既然是设计题而且设计的是链表那么自然而然想起与之相对应的数组所以这里是用数组类模拟链表的这里设计了获取链表第 k 个值添加头添加尾添加 index 位置的节点以及删除第 index 节点的 api按要求设计即可注意边界即可
/** * 分析 * 1. 这里是用数组来模拟链表 */
var MyLinkedList function () {this.data [];
};/** * 分析 -- 获取第 index 个节点的值 * 1. 这里的 index 类比数组的下标值是从 0 开始的也就是 index 为 0 代表头节点 * 2. 这里是获取第 index 个节点的值如果没有这个 index即 index 超出链表长度 len-1返回 -1 */
MyLinkedList.prototype.get function (index) {const size this.data.length;return index size ? this.data[index] : -1;
};/** * 分析 -- 从头部插入一个链表值 */
MyLinkedList.prototype.addAtHead function (val) {this.data.unshift(val);
};/** * 分析 -- 从尾部插入一个链表值 */
MyLinkedList.prototype.addAtTail function (val) {this.data.push(val);
};/** * 分析 -- 从 index 插入一个值 */
MyLinkedList.prototype.addAtIndex function (index, val) {const len this.data.length;if (index len) {if (index 0) {this.data.unshift(val);} else if (index len) {this.data.push(val);} else {this.data.splice(index, 0, val); //在 index 节点删除 0 个值并加入 val}}
};/** * 分析 -- 删除第 index 个值 */
MyLinkedList.prototype.deleteAtIndex function (index) {const len this.data.length;if (index 0 index len) {this.data.splice(index, 1);}
};
1171. 从链表中删去总和值为零的连续节点
分析 – 暴力解法
直接两个循环遍历链表得到所有链表组合的和遇到 0 的刷新外层指针的 next 达到删除的效果类比于数组相当于将数组中和为 0 的连续子数组删除得到剩下的数组所以可以开两个循环动态获取数组的长度一旦遇到符合要求的数组就删除直到外层遍历结束为止画图会比较容易看到值得注意的是一定要有一个指针 outer 从 head - tail , 然后每一次都有临时指针 inner 从 outer.next 开始走到 tail最差就不需要删除所以要走 123…n O(N2)
var removeZeroSumSublists function (head) {let emptyNode new ListNode();emptyNode.next head;let sum 0;let outer emptyNode;while (outer) {let inner outer.next;while (inner) {// 每次都由 inner 来判断是否要删除相应的链表// outer 相当于是外围的一个 prev 指针一旦某一个链表需要删除直接 outer.next 删除节点的下一个节点 即可sum inner.val;inner inner.next;if (sum 0) {// outer - inner 的节点都要删除outer.next inner;sum 0; //返回}}// outer 也需要不断遍历到 tailouter outer.next;// 每一次遍历时临时总和要重置sum 0;}return emptyNode.next;
};
1019. 链表中的下一个更大节点
分析 – 双指针
写指针 w 遍历整个链表读指针 r 找到第一个比当前 w 大的节点并返回对应的值如果 r 走完整个链表没找到则返回 0这题和上一题一样都是循环遍历找到符合要求的值然后直接返回时间复杂度 O(n2)
var nextLargerNodes function (head) {if (!head) return [];let ret [];while (head) {let r head.next;let temp 0;while (r) {if (r.val head.val) {temp r.val;break;}r r.next;}ret.push(temp);head head.next;}return ret;
};
1669. 合并两个链表
分析
用 list2 来替换链表 a-b需要注意这里的 a 和 b 是下标为 a,b 的节点第一个节点的坐标为 0可以类比数组的下标找出 a 的前缀节点 prev 和 b 的下一个节点 next然后用 prev.next list2, 遍历 list2 到 tail2, tail2.next next 即可这里 list1 和 list2 的长度已经做了限制所以不需要做边界了时间复杂度 O(nm)
var mergeInBetween function (list1, a, b, list2) {const emptyNode new ListNode();emptyNode.next list1;let prev (next emptyNode);//这个时候 prev 和 next 都是空节点而 list1 的 head 节点对应的 index 是0所以初始化为 -1let index -1;// 不取 的时候得到的就是 下标为 b 的节点while (index b) {if (index a - 1) {// 这里是为了取下标为 a 节点的前一个节点 prevprev prev.next;}next next.next;index;}// 这个时候 index 是b1, 所以 next 是 b 的下一个节点// 插入 list2prev.next list2;while (list2 list2.next) {list2 list2.next;}// 这个时候的 list2 已经到了 taillist2.next next;return emptyNode.next;
};
剑指 Offer 35. 复杂链表的复制
分析
因为要复制一个链表所以所有 head 上节点其实都已经不能使用了需要重新创建新的 Node 节点然后对应的 next 和 random 也需要是新的节点而不是 head 已经保存好的。因为新的节点 next 指针指向的节点还没创建对应的 random 节点无法确定所以使用 map 先保存一份单个值的节点其中 key 是旧的 Node 节点value 是新创建的节点然后再遍历 head 链表找到就节点的复制节点为它指向新的 next 和 random这里为啥用 weakMap 而不是 map 呢这就是面试的另外一个问题了可以查看一下 map 和 weakMap 的区别这里主要是和 key 为对象时消除 map 后的垃圾回收机制有关时间复杂度O(N)
var copyRandomList function (head) {if (!head) return head;const map new WeakMap();let temp head;while (temp) {// key 是旧节点value 保存一个新的节点map.set(temp, new Node(temp.val));temp temp.next;}// 开始复制temp head;while (temp) {const node map.get(temp); //这个是一个新的节点它的 next 和 random 也要是新的存在 map 中node.next map.get(temp.next) || null;node.random map.get(temp.random) || null;temp temp.next;}return map.get(head);
};
25. K 个一组翻转链表
既然是翻转肯定是需要用到空节点;一次遍历计算链表长度看看需要翻转多少次因为需要翻转多次每一次翻转需要用到的变量:outerPrev – 每一次翻转前一个节点用来和翻转后的头节点连接cur 表示的翻转链表时当前节点prev 是遍历到的前一个节点step 表示翻转了多少次由于初始化时 cur 是第一个节点所以可以翻转 k 次翻转结束后cur 表示下一次翻转的头节点prev 是翻转后的头节点tempHead 是保存起来的翻转前头节点现在是翻转后的尾节点也是下一轮翻转的前一个节点所以将他们连接起来 outerPrev.next prevtempHead.next cur;更新一下 outerPrev时间复杂度 O(N)
var reverseKGroup function (head, k) {if (!head.next || k 2) return head;const emptyNode new ListNode();emptyNode.next head;let len 0;let cur head;while (cur) {len;cur cur.next;}let count Math.floor(len / k); //需要翻转的次数cur head;let outerPrev emptyNode; //每次翻转链表的前一个节点while (count--) {let tempHead cur; // 翻转链表的临时链表头let prev outerPrev;let step 0; //每一次翻转走的步数while (step k) {const next cur.next;cur.next prev;prev cur;cur next;step;}// 翻转好了外部prev 和翻转后的头节点相连outerPrev.next prev;tempHead.next cur;// 更新外部prev 为临时头节点outerPrev tempHead;}return emptyNode.next;
};
