Reverse Nodes in k-Group 以K个节点为一组反转链表

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

Follow up:

Could you solve the problem in O(1) extra memory space?
You may not alter the values in the list's nodes, only nodes itself may be changed.

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

就是给你一个链表，k个为一组进行反转，最后不够k的就不反转了，而且k肯定小于表长。

问题

把大象塞到冰箱要几步？

分解问题，

1 首先判断这个链表有没有K个元素
2 开始分段反转
3 判断是否反转结束

虚头法 dummy head+递归

reverseN用来判断从head开始是否足够n个节点进行反转，如果不够就不处理，否则就会调用realreverseN进行反转【realreverseN将从传入的head开始的n个节点进行反转处理】，reverseN返回的是从传入的head开始到第n个节点反转后的头节点。如果reverseN最后返回的节点和p.next是同一节点表示反转结束，否则就要让p.next指向返回的节点，继续N个节点的反转处理。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseN(ListNode head,int n){
        ListNode p =head;
        int count  = n-1;
        while(count>0&&p!=null){
            p= p.next; count--;
        }
        if(p==null){ return head;}
        return realreverseN(head,n);
   }

    public ListNode realreverseN(ListNode head,int n){
        if(n==1){return  head;}
        ListNode tail = head.next, p = realreverseN(head.next,n-1);
        head.next=tail.next;
        tail.next =head;
        return p;
    }
    
    public   ListNode reverseKGroup(ListNode head, int k) {
        ListNode ret = new ListNode(0, head),p=ret,q=p.next;
        while ((p.next=reverseN(q,k))!=q){
            p =q;
            q =p.next;
        }
        return ret.next;
    }
}