前言

上一章连接【链表反转问题】
上一章已经讲过了单向链表的反转，接下来我们在上一章的基础上来一道进阶题：
每K个一组反转链表

问题描述

问题连接：【每K个一组反转链表】
描述
给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。

说明：

1. 你需要自行定义链表结构，将输入的数据保存到你的链表中；
2. 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换；
3. 你的算法只能使用常数的额外空间。

输入描述：
第一行输入是链表的值
第二行输入是K的值，K是大于或等于1的整数

输入形式为：
1 2 3 4 5
2

输出描述：
当 k = 2 时，应当输出:
2 1 4 3 5

当 k = 3 时，应当输出:
3 2 1 4 5

当k=6时，应当输出：
1 2 3 4 5

示例1
输入：
1 2 3 4 5
2
输出：
2 1 4 3 5

解题思路

我们上一章做的是 两个两个交换 ，而这道题是k个k个交换，其实都是差不多的
解这道题的大致思路为：

1. 选出前k个节点
2. 先反转前k个节点组成的链表
3. 剩余节点组成的链表，我们可以看成一个新的链表，
4. 就可以将“反转剩余节点的链表”看成一个的子问题

说到子问题相信大家都知道要用递归求解了

在上代码之前，希望大家有上一章反转单链表的基础，不然代码可能不是太好理解。传送门->【链表反转问题】

代码实现

import java.util.*;
class ListNode{
    int val;
    ListNode next = null;
    ListNode(int val){
        this.val = val;
    }
}
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        // 接收输入的第一行数据
        String str = sc.nextLine();
        // 以 一个空格 为界 分开这些数字
        String[] strArr = str.split(" ");
        // 创建链表的头结点
        ListNode head = new ListNode(-1);
        ListNode rear = head;   // rear为节点
        // 将数据都插入到单向链表中
        for(String item: strArr) {
            ListNode newNode = new ListNode(Integer.parseInt(item));
            // 插入节点 （尾插法）
            rear.next = newNode;
            rear = newNode;
        }
        // 接收输入的k
        int k = sc.nextInt();
        // 调用我们的反转方法
        ListNode newHead = reverse(head.next, k);
        // 输出反转后的链表
        ListNode cur = newHead;
        while(cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
    }

    /** * 以k个节点为一组 分组反转单向链表 */
    public static ListNode reverse(ListNode head, int k){
        // 特殊情况一：【链表为null 或者 k<=1, 没必要反转】
        if(head == null || k <= 1) {
            return head;
        }
        // cur 指向当前节点
        ListNode cur = head;
        // 下面这一段代码主要用来判断， 链表长度是否小于k
        for(int i=1; i<k && cur!=null; i++) {// 注意这里i初始值为1， 条件是i<k,相当于cur后移了k-1步
            // cur后移
            cur = cur.next;
        }
        // 特殊情况二 ：【链表剩余长度不足k，不用反转】
        // 如果cur为null 则说明上面跳出for循环的原因是: 链表的长度不足k,题目要求不用反转，直接返回head即可
        if(cur == null) {
            return head;
        }

        // 排除完特殊情况 下面就是正常情况了。 此时cur已经指向第k个节点了
        // 先保存下一节点（k+1）地址 ， 因为接下来要断开 cur与k+1 节点的连接
        ListNode nextListHead = cur.next;
        // 断开k节点 与 k+1节点的连接 因为接下来要单独反转当前组单链表了
        cur.next = null;
        // 反转当前组 单项链表
        ListNode newHead = reverse(head);
        // 递归处理后面链表
        ListNode newNextHead = reverse(nextListHead,k);
        // 重新连接之前断开的链表
        head.next = newNextHead;    // 这里的head 其实已经被反转到后面了，现在是第k个节点
        // 返回反转后的新头节点
        return newHead;
    }

    /** * 反转整个单向链表 */
    public static ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode next_ = null;

        while(cur != null) {
            // next_指向当前节点的下一个节点
            next_ = cur.next;
            // 开始局部反转 当前节点的next域指向前一节点
            cur.next = pre;
            // pre指针后移
            pre = cur;
            // cur指针后移
            cur = next_;
        }
        return pre;
    }
}

在代码中每一步我都有详细的注解，如果你有耐心看完的话肯定会理解的。（一遍没看明白可以多看几遍）