Given the head of a linked list, 
reverse the nodes of the list k at a time, 
and return the 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.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

Example 1:

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

Example 2:

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

 
Constraints:
* The number of nodes in the list is n.
* 1 <= k <= n <= 5000
* 0 <= Node.val <= 1000

import util.ListNode;


public class Solution {


    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next=new ListNode(2);
        head.next.next=new ListNode(3);
        head.next.next.next=new ListNode(4);
        head.next.next.next.next=new ListNode(5);
        System.out.println(reverseKGroup(head,3));
    }


    /**
     * @param head,k
     * The number of nodes in the list is n. 1 <= k <= n <= 5000
     * 0 <= Node.val <= 1000
     * 几乎就是24的翻版，所以主体的逻辑也要是24的翻版
     * */
    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode cur= head;


        for (int i = 0; i < k-1; i++) {
            cur = cur.next;
            if (cur == null) return head;
        }
        ListNode next=cur.next;
        ListNode newHead = reverse(head,cur);
        head.next =reverseKGroup(next,k);
        return newHead;
    }


    /**
     * 1->2->3->4
     * 4->3->2->1
     * 采用的是头插法，变化为4->1,4->2->1,4->3->2->1
     * 传入之前为链表的前后两个节点
     * 一番操作后，还是那两个节点，只不过成员变量发生了变化
     * */
    private static ListNode reverse(ListNode head, ListNode end) {
        ListNode newHead = end;
        while(head != end){
            ListNode tmp = head.next;
            head.next=end.next;
            end.next=head;
            head = tmp;
        }
        return newHead ;
    }
}