题目

类型：Linked List

难度：困难

K 个一组翻转链表 - 图1

解题思路

这题不涉及复杂的算法，但是需要考虑的细节比较多。

1、需要把链表节点按照 k 个一组分组，所以可以使用一个指针 head 依次指向每组的头节点。这个指针每次向前移动 k 步，直至链表结尾。对于每个分组，先判断它的长度是否大于等于 k。如果是，就翻转这部分链表，否则不需要翻转。

2、对于一个子链表，除了翻转其本身之外，还需要将子链表的头部与上一个子链表连接，以及子链表的尾部与下一个子链表连接。因此，在翻转子链表的时候，我们不仅需要子链表头节点 head，还需要有 head 的上一个节点 pre，以便翻转完后把子链表再接回 pre。但是对于第一个子链表，它的头节点 head 前面是没有节点 pre 的。所以需要新建一个节点，把它接到链表的头部，让它作为 pre 的初始值，这样 head 前面就有了一个节点，可以避开链表头部的边界条件。

3、反复移动指针 head 与 pre，对 head 所指向的子链表进行翻转，就得到了答案。

4、返回头节点的前面 的节点pre 即可

代码

  1. class Solution {
  2.     public ListNode reverseKGroup(ListNode head, int k) {
  3.         ListNode hair = new ListNode(0);
  4.         hair.next = head;
  5.         ListNode pre = hair;
  7.         while (head != null) {
  8.             ListNode tail = pre;
  9.             // 查看剩余部分长度是否大于等于 k
  10.             for (int i = 0; i < k; ++i) {
  11.                 tail = tail.next;
  12.                 if (tail == null) {
  13.                     return hair.next;
  14.                 }
  15.             }
  16.             ListNode nex = tail.next;
  17.             ListNode[] reverse = myReverse(head, tail);
  18.             head = reverse[0];
  19.             tail = reverse[1];
  20.             // 把子链表重新接回原链表
  21.             pre.next = head;
  22.             tail.next = nex;
  23.             pre = tail;
  24.             head = tail.next;
  25.         }
  27.         return hair.next;
  28.     }
  30.     public ListNode[] myReverse(ListNode head, ListNode tail) {
  31.         ListNode prev = tail.next;
  32.         ListNode p = head;
  33.         while (prev != tail) {
  34.             ListNode nex = p.next;
  35.             p.next = prev;
  36.             prev = p;
  37.             p = nex;
  38.         }
  39.         return new ListNode[]{tail, head};
  40.     }
  41. }