上回说到的是单链表反转的“二哥” —— 两两替换链表中的节点。明天来剖析一下它的大哥：“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。