题目
给你链表的头节点
head，每k个节点一组进行翻转，请你返回修改后的链表。
k是一个正整数，它的值小于或等于链表的长度。如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
提示：
链表中的节点数目为
n
1 <= k <= n <= 5000
0 <= Node.val <= 1000https://leetcode.cn/problems/reverse-nodes-in-k-group/solutions/
解题思路
k 个分为一组。k 个节点进行反转。下面就主体流程中的每一步拆开来分析：
1. 分组：从起始点往后走 k-1步为一组，返回最后一个节点 end。不够 k-1 步返回 null（不进行第二步反转，直接和前面的组连接起来）。代码如下：
// 循环遍历链表中的每个节点while(head != null){// 获取分组中的最后一个节点ListNode end = getEnd(head, k);if(end == null){// 不够 k 个节点直接返回。break;}// 刚好取得 k 个节点，[head, end]。这里就可以准备进入第二步。// 下一组的开头ListNode nextGroupHead = end.next;// head 指向下一组的开头，查找下一组。head = nextGroupHead;}
3. 连接反转后的每一组：每组反转后的节点 end 变为开头，head 变为结尾。要想连接每一组，需要将上一组的head 指向下一组反转后的开头（即下一组的end），这里需要考虑临界值，因为第一组没有上一组，所以我们可以开一个保护节点protect。
完整代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode protectNode = new ListNode(0);ListNode lastGroupTail = protectNode;// 1. k个1组，进行分组while(head != null){ListNode end = getEnd(head, k);if(end == null){// 不够 k 个元素直接返回, 跳出循环，无需反转。break;}// 下一组的开头ListNode nextGroupHead = end.next;// 2. 每组进行内部反转链表// [head, end] 为一组, 进行反转。this.reverse(head, end);// 3. 将反转后的列表连起来lastGroupTail.next = end;head.next = nextGroupHead;lastGroupTail = head;// head 指向下一组的开头，查找下一组。head = nextGroupHead;}return protectNode.next;}private ListNode reverse(ListNode head, ListNode end){ListNode pre = null;ListNode stop = end.next;// 这不能使用 wile(head != end.next), 因为循环内部会将end.next反转。while(head != stop){ListNode nextNode = head.next;head.next = pre;pre = head;head = nextNode;}return pre;}/*** 根据 head 向后找第 k - 1 个元素为 end, 如果不够 k 个元素直接返回null, 不用反转。*/private ListNode getEnd(ListNode head, int k){while(head != null){k--;if(k == 0){return head;}head = head.next;}return null;}}
复杂度分析
时间复杂度O(n)：getEnd 每次循环k次，最后一次 <= k，但是总体加起来是 n。reverse 每次的时间复杂度也是 k，加以来 <= n，因为最后一组可能需要反转。总的时间复杂度约为 2n, 忽略常数后为 O(n)；
空间复杂度O(1)：额外开启的变量都是常数级的，所以空间复杂度为O(1)。
本篇文章来源于微信公众号: i余数
微信扫描下方的二维码阅读本文
Comments NOTHING