这个题目应该比较经典，虽说是hard级别，可是并没有那么难。下面看一下我的解法和经典的解法。
1. 我的解法（费时费力）
既然是逆转，我先想到的是使用栈，比如三个为一组，那么我只要把这三个节点往栈里放，然后依次弹出并连接不就好了，然后弹出最后一个后再递归进行后面此类操作。当然，这个写起程序来还是比较简单无脑的，但是费时费力，因为用到了递归，如果链表很长…不能想象。不过还是要上一下代码：
public ListNode reverseKGroup(ListNode head, int k) {
Stack<ListNode> stack = new Stack<>();int num = k;ListNode oldHead = head; //记住旧链表的头，以便没有k个元素时直接返回while (head != null && num > 0) {
stack.push(head);head = head.next;--num;}if (num > 0) //最后一组节点数量小于k个，直接返回原链表的头结点return oldHead;ListNode nextHead = head; //因为上一步中head若满足则一定指向下一个链表的头ListNode newHead = stack.pop(), p = newHead; //逆转后新链表的头部为栈顶while (!stack.empty()) {
//将栈中剩余元素连接起来p.next = stack.pop();p = p.next;}p.next = null; //中断最后一个节点的nextp.next = reverseKGroup(nextHead, k); //递归逆转后面的链表return newHead; //返回新的}
2. 经典解法（省时省力）
其实经典解法说起来也就是没有用递归，而只需要循环遍历就行，也不难理解。关键的思路在于逆转链表的时候要使用头插法。记住某一个子链表的头结点，然后一个指针向后移动，并将这个指针所指的节点进行头插即可。只是这个过程因为要记住的东西太多了，所以定义的临时变量会有点多，但是思路确是比较容易理解的。代码如下：
public ListNode reverseKGroup(ListNode head, int k) {
ListNode begin;if (head==null || head.next ==null || k==1)return head;ListNode dummyhead = new ListNode(-1);dummyhead.next = head;begin = dummyhead;int i=0;while (head != null){
i++;if (i%k == 0){
begin = reverse(begin, head.next);head = begin.next;} else {
head = head.next;}}return dummyhead.next;}public ListNode reverse(ListNode begin, ListNode end){
ListNode curr = begin.next;ListNode next, first;ListNode prev = begin;first = curr;while (curr!=end){
next = curr.next;curr.next = prev;prev = curr;curr = next;}begin.next = prev;first.next = curr;return first;}
2020.2.20更
3.更简洁好看的
我不知道为什么已经看不懂第二种是什么鬼了，分享一下看到的更容易懂的解法。首先我们要有一个函数翻转部分链表，在反转链表中我们讲过迭代的方法，它是翻转整个链表，那么我们把结束的条件改一下，就可以让它翻转部分链表，代码如下：
/** 反转区间 [a, b) 的元素，注意是左闭右开 */
ListNode reverse(ListNode a, ListNode b) {
ListNode pre, cur, nxt;pre = null; cur = a; nxt = a;// while 终止的条件改一下就行了，也就是说我们对于b是不进行翻转的while (cur != b) {
nxt = cur.next; //先把下一个存起来，更新nxtcur.next = pre; //翻转pre = cur; //更新pre和curcur = nxt;}// 返回反转后的头结点return pre;
}ListNode reverseKGroup(ListNode head, int k) {
if (head == null) return null;// 区间 [a, b) 包含 k 个待反转元素ListNode a, b;a = b = head;for (int i = 0; i < k; i++) {
// 不足 k 个，不需要反转，base caseif (b == null) return head;b = b.next;}// 反转前 k 个元素，此时区间为[a,b)，而且新的尾结点就是原来的头结点aListNode newHead = reverse(a, b);// 递归反转后续链表并连接起来，即将尾结点a.next指向后面的翻转a.next = reverseKGroup(b, k);return newHead;
}