k个一组反转链表

1.理解题意

我们需要将一个链表，按每k个为一组进行反转，不足k个的组不进行反转。

2.解题步骤

1. 检查当前链表够不够分组
   • 不够分成k个，直接返回当前链表的头结点
   • 够分成k个，则继续
2. 反转当前链表的前K个结点
3. 反转下一组的前K个结点

上面是基本的步骤，其中还有一些细节问题，需要探究。

1. 反转后怎么进行连接呢？要定义什么变量保存结点信息？

这是问题的关键，因为反转后会返回反转链表的头结点，所以需要保存这个结点用于返回，那么返回后由谁来接收呢？需要上一个反转的链表的尾部来接收，这样才能将各自反转的链表连接在一起。

1. 怎么反转前K个结点？需要什么参数？

反转链表前K个结点的方式就两种，一种是递归方式，一种是迭代方式。

需要的参数取决于我们如何判断结束的条件，可以用K，也可以使用第K个结点或者是第K+1个结点，都没有问题，这和用递归方式还是迭代方式无关。

关于反转前K个结点详情看

3.具体代码

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null) return null;
        // 要有两个变量
        //一个用来指向当前的头结点，用来在反转后指向后面的链表
        //一个用来传递给下一组要反转的链表
        ListNode a, b;
        a = b = head;
        //1.检查当前链表的结点数还够不够反转
        for(int i = 0; i < k; i++){
            if(b == null) return head;
            b = b.next;
        }
        //2.反转当前链表的前k个结点
        ListNode newHead = reverseK(a, b);
        //3.继续反转下一组链表
        a.next = reverseKGroup(b, k);
        return newHead;
    }
    //传入第K+1个结点作为结束条件（迭代）
    public ListNode reverseK(ListNode a, ListNode b){
        ListNode prev, cur, nxt;
        prev = null; cur = nxt = a;
        while(cur!=b){
            nxt = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nxt;
        }
        return prev;
    }
    //传入K作为结束条件（迭代）
    public ListNode reverseK(ListNode a, int n){
        ListNode prev, cur, nxt;
        prev = null; cur = nxt = a;
        while(n-- != 0){
            nxt = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nxt;
        }
        return prev;
    }
    //传入K作为结束条件（递归）
    public ListNode reverseK(ListNode a, int n){
        if(n == 1){
            return a;
        }
        ListNode Last = reverseK(a.next, n-1);
        ListNode tail = a.next.next;
        a.next.next = a;
        a.next = tail;
        return Last;
    }
    //传入第K+1个结点作为结束条件（递归）
    public ListNode reverseK(ListNode a, ListNode b){
        if(a.next == b) return a;
        ListNode Last = reverseK(a.next, n-1);
        ListNode tail = a.next.next;
        a.next.next = a;
        a.next = tail;
        return Last;
    }
}