共计 2749 个字符，预计需要花费 7 分钟才能阅读完成。
上回说到的是单链表反转的“二哥”—— 两两替换链表中的节点。明天来剖析一下它的大哥：“K 个一组翻转链表”。
题目形容如下。
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最初残余的节点放弃原有程序。
示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，该当返回: 2->1->4->3->5
当 k = 3 时，该当返回: 3->2->1->4->5
如果一上来就做 K 个一组翻转链表这个题，难度还是比拟大的，如果后面有了它两个弟弟的铺垫，那么这道题目就是瓜熟蒂落的了，后面两道题目的答案联合起来就是这道题目的答案了。这道题目和它两个兄弟一样，也能够应用迭代和递归两种办法解决。
办法一：三指针迭代
有了上回单链表反转的双指针迭代法的根底，再来解决它二哥，就绝对容易很多了。
“巧妇难为无米之炊”。题目中说的是 K 个一组翻转，那首先得有 K 个节点才行，和“两两替换链表中的节点”一样，上来先判断够 K 个节点才持续替换，而且循环持续的条件也是要满足剩下的节点够 K 个才行。
咱们能够应用两个变量 left 和right来示意以后要进行翻转的一段链表中的起始节点和完结节点。
如上图，指针 L 和R别离示意一段要进行翻转的链表中的起始节点和完结节点，如何找到一段链表中的第 K 个节点，咱们能够写一个办法来实现，如果剩下的链表的长度够 K 个，就返回第 K 个节点的指针，反之返回null：
private ListNode findKthNode(ListNode p, int k) {
int curCount = 0;
while (curCount < k - 1 && p != null) {
p = p.next;
curCount++;
}
return (curCount == k - 1) ? p : null;
}指针 L 和R之间的节点怎么进行翻转，和链表反转全家桶（一）：动画详解单链表反转中的办法是一样的，惟一区别是“单链表反转”中完结的指针是尾指针，而这里完结的指针是指定的 —— 每段链表的第 K 个节点。有迭代和递归两种，为了放弃办法的一致性，这里还用迭代法。实现代码如下：
private void reverseRange(ListNode left, ListNode right) {if (left == right) {return;}
ListNode exit = right.next;
ListNode cur = left, pre = null;
while (cur != exit) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
}同时，要思考上面的这种场景，第一段的 K 个节点曾经实现翻转，当初轮到第二段链表进行翻转，实现之后，pre须要指向 R 节点，所以还要记录每一轮替换的前驱节点，下图这个例子外面前驱节点就是节点 1。
整体的代码实现如下：
class Solution {public ListNode reverseKGroup(ListNode head, int k) {if (head == null || head.next == null) {return head;}
ListNode pre = null, left = head, right = findKthNode(head, k);
if (right == null) {return head;}
ListNode ans = right;
while (left != null && right != null) {
ListNode next = right.next;
reverseRange(left, right);
left.next = next;
if (pre != null) {pre.next = right;}
pre = left;
left = next;
right = findKthNode(next, k);
}
return ans;
}
private void reverseRange(ListNode left, ListNode right) {if (left == right) {return;}
ListNode exit = right.next;
ListNode cur = left, pre = null;
while (cur != exit) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
}
private ListNode findKthNode(ListNode p, int k) {
int curCount = 0;
while (curCount < k - 1 && p != null) {
p = p.next;
curCount++;
}
return (curCount == k - 1) ? p : null;
}
}察看一下下面的代码，它和“两两替换链表中的节点”的构造是一样的。下图为代码比照，能够看到 1，2，3 处的代码模式是一样的，“两两替换链表的节点”是“K 个一组翻转链表”在 K=2 时的特例。
复杂度剖析
- 工夫复杂度：
O(n)。 - 空间复杂度：
O(1)。
办法二：递归
递归法同样是它的两个小弟的联合。
一个链表段内的翻转的递归写法和“单链表的翻转”是一样的，惟一不同点是递归退出条件不同，链表段的翻转递归退出条件是左指针和右指针相遇，而单链表反转的退出条件是以后节点为空或以后节点曾经是尾节点。
同样，它的整体写法和“两两替换链表中的节点”是一样的，“两两替换链表中的节点”是“K 个一组翻转链表”在 K 为 2 时的特例。
代码如下：
class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode left = head, right = findKthNode(head, k);
if (right == null) {return left;}
ListNode next = reverseKGroup(right.next, k);
reverseRange(left, right);
left.next = next;
return right;
}
private void reverseRange(ListNode left, ListNode right) {if (left == right) {return;}
reverseRange(left.next, right);
left.next.next = left;
left.next = null;
}
private ListNode findKthNode(ListNode p, int k) {
int curCount = 0;
while (curCount < k - 1 && p != null) {
p = p.next;
curCount++;
}
return (curCount == k - 1) ? p : null;
}
}复杂度剖析
- 工夫复杂度：
O(n)。 - 空间复杂度：
O(n)，应用了递归，递归的栈深度为n。
