苏州建设网站市政中标项目,网络推广渠道和方式,网站放自己服务器备案,做网站需要会什么 知乎文章目录 前言链表反转|K个一组翻转链表解题方法#xff1a;头插法处理#xff1a;穿针引线法处理#xff1a; 总结 前言
提示#xff1a;没有人天生就喜欢一种气味而讨厌另一种气味。文明的暗示而已。 链表反转|K个一组翻转链表
给你链表的头节点 head #xff0c;每 k… 文章目录 前言链表反转|K个一组翻转链表解题方法头插法处理穿针引线法处理 总结 前言
提示没有人天生就喜欢一种气味而讨厌另一种气味。文明的暗示而已。 链表反转|K个一组翻转链表
给你链表的头节点 head 每 k 个节点一组进行翻转请你返回修改后的链表。
k 是一个正整数它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。 进阶你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗
思路来的很快重点是代码层面的编写这个很重要思路呢就是常见的头插法和穿针引线法来处理数组反转问题当然今天我们也是采用这两种方法解决的那就开始实现他吧
解题方法
头插法处理
头插法重点在理解虚拟节点上如果这个问题解决了相比较而言要比穿针引线要好实现的多 我们试着把链表整体分为3段一段是已经翻转的一端是正在反转一端是未反转的。为了方便翻转我们需要京链表遍历一边统计一下链表的长度len然后将链表进行分组nlen/k,接下来就是循环进行分组翻转链表。 我们尝试这画一些图能够更有里的说明 结假设我们开始翻转 4 节点 具体思路
找到链表的长度 len 分组cur.next cur.next.next; next.next pre.next; pre.next next;循环下一次
上代码 /*** 方法2头插法** param head* param k* return*/public static ListNode reverseKGroup2(ListNode head, int k) {ListNode dummyNode new ListNode(-1);dummyNode.next head;ListNode cur head;int len 0;while (cur ! null) {cur cur.next;len;}int n len / k; // 计算出来分几组ListNode pre dummyNode;cur head;for(int i 0; i n; i) {for(int j 0; j k - 1; j) { // k - 1 画图就知道了ListNode next cur.next;cur.next cur.next.next;next.next pre.next;pre.next next;}pre cur; cur cur.next; // 记得修改指针}return dummyNode.next;}穿针引线法处理
这个思路可以回顾一下穿针引线到底是怎么回事
首先还是将链表分组翻转 我们就可以一组一组的处理把他们分成已经翻转的、正在翻转的和未翻转的三部分同时为了方便处理头节点我们使用了一个虚拟的节点。
接下来就是遍历根据k个为一组找到四个关键位置并使用变量perstartendnext标记比如下面的图 接着我们就开始翻转对应颜色进行翻转我们将end.next null ,直接使用链表翻转复用链表翻转的常规操作。注意指针的变化head便是传入方法的参数我们接着看图
当然翻转之后我们接下来就是将原始链表缝起来这就需要调整指针域同样这里也要注意指针的变化 接着调整指针进行下一次循环 总结一下
遍历找到四个关键位置复用常规翻转链表pre.next end; start.next next; 调整指针域调整下一次循环
了解上面的图代码应该也会写吧 /*** 方法1: 穿针引线法** param head* param k* return*/public static ListNode reverseKGroup(ListNode head, int k) {ListNode dummyNode new ListNode(-1);dummyNode.next head;ListNode pre dummyNode;ListNode end dummyNode;while (end.next ! null) { // 最终结束的地方for (int i 0; i k end ! null; i) {end end.next; // 找到当前分组的最后一个}if (end null) {break;}// 找到start nextListNode start pre.next;ListNode next end.next;end.next null; // 思考pre.next reverse(start);start.next next;pre end;// 调整下一次循环end pre;}return dummyNode.next;}复习一下链表反转
private static ListNode reverse(ListNode head) {ListNode pre null;ListNode cur head;while(cur ! null) {ListNode next cur.next;cur.next pre;pre cur;cur next;}return pre;}总结
注意指针域的变化多画图更容易理解链表反转重点重点重点
