本文主要介绍如何把一个链接分成K个节点的N组，并对每个组的链表进行翻转。

需求描述

给出一个单链表的头结点head和一个整数k，将这个单链表实现k个节点的小组，并对小组内部进行链表反转，如果最后一组不够k个节点的话，最后一组则保存原样不动。

示例：

• 调整前的单链表：1->2->3->4->5->6->7->8，k为3。
• 调整后的单链表：3->2->1->6->5->4->7->8。

思路分析

要实现这个功能的话，我们需要考虑以下几点：

1. 把链表进行分组
2. 判断最后一组的节点是否为k个
3. 对每一组的链表进行反转操作
4. 如何把两组之间的节点串联起来
5. 返回一个新的头结点

先看下两组之间的连接，假设现在要操作的这组数为[M,N]，上一组的结尾为X，下一组的开头为Y，那要怎么操作呢？

1. 首先把这一组数据[M,N]进行反转，变为[N,M]
2. 让X节点的next指针执行N
3. 让M节点的next指针指向Y
4. 让M节点作为X再去执行下一轮操作

对于每组k个节点，我们可以实现一个函数，传进去一个节点以及k，返回这个节点后第k个节点即可，返回的这个节点是每组的最后一个节点，用来每组直接的链表拼接使用。

然后是组内k个节点的链表反转，在反转的时候需要注意，怎么处理好两个组之间的指向关系，这一块很容易弄晕，我们可以设计一个函数，这个函数接收两个节点参数，用来实现这两个节点之间链表的反转。

代码实现

首先定一下链表节点，代码如下：

public class ListNode {
   public int val;
   public ListNode next;
}

再来实现下分组的函数，返回每组的最后一个节点，这个函数是反馈给出节点后的第k个节点，如果不足k个节点的话则返回null，代码如下：

public ListNode getKGroupEnd(ListNode start, int k) {
   while (--k != 0 && start != null) {
      start = start.next;
   }
   return start;
}

链表反转函数，这个函数不考虑这两个节点前后是什么样子的，有没有节点指向start节点也不关心，只负责把链表进行反转，代码如下：

public void reverse(ListNode start, ListNode end) {
   end = end.next;
   ListNode pre = null;
   ListNode cur = start;
   ListNode next = null;
   while (cur != end) {
      next = cur.next;
      cur.next = pre;
      pre = cur;
      cur = next;
   }
   start.next = end;
}

分组以及组内链表反转的代码已经有了，只剩下处理组之间的是如何连接的了，来看一下代码：

public ListNode reverseKGroup(ListNode head, int k) {
   ListNode start = head;
   ListNode end = getKGroupEnd(start, k);
   // 总结点不足k个
   if (end == null) {
      return head;
   }
   head = end;
   reverse(start, end);
   ListNode lastEnd = start;
   while (lastEnd.next != null) {
      start = lastEnd.next;
      end = getKGroupEnd(start, k);
      if (end == null) {
         return head;
      }
      reverse(start, end);
      lastEnd.next = end;
      lastEnd = start;
   }
   return head;
}

在这个方法中，定义一个head用来记录第一组链表的最后一个节点，这个节点最后会变成每组都处理后的头结点。

lastEnd是用来记录上一组的最后一个节点，为啥是start呢？因为在反转后，start就变成了最后一个节点，用lastEnd记录一下，方便与下一组链表进行关联，这样几次循环之后，整个链接就变成了目标的样子，每组反转组组连接形成了一个新的链表。

总结

本文主要介绍如何把一个链接分成K个节点的N组，并对每个组的链表进行翻转，本次题目的需求还是比较简单的，复杂的是如何处理链表指针的指向关系，这个指向关系需要费点脑细胞啊 ^_^

作者：Java星辰
链接：https://juejin.cn/post/7222282849553252389
来源：稀土掘金