package com.company;


import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (k <= 1) {
            return head;
        }

        ListNode ret = new ListNode(0);
        ret.next = head;

        ListNode cur = ret;
        ListNode next = head;
        ListNode first = null;
        ListNode second = null;
        ListNode third = null;
        while (true) {
            int i=0;
            for (; i<k; i++) {
                if (next == null) {
                    break;
                }
                next = next.next;
            }
            if (i < k) {
                break;
            }

            first = cur.next;
            second = first.next;
            for (i=0; i<k-1; i++) {
                third = second.next;
                second.next = first;
                first = second;
                second = third;
            }
            cur.next.next = next;
            third = cur.next;
            cur.next = first;
            cur = third;
        }

        return ret.next;
    }
}

public class Main {

    public static void main(String[] args) throws InterruptedException {

        System.out.println("Hello!");
        Solution solution = new Solution();

        // Your Codec object will be instantiated and called as such:
        ListNode ln1 = new ListNode(1);
        ListNode ln2 = new ListNode(2);
        ListNode ln3 = new ListNode(3);
        ListNode ln4 = new ListNode(4);
        ListNode ln5 = new ListNode(5);
        ln1.next = ln2;
        ln2.next = ln3;
        ln3.next = ln4;
        ln4.next = ln5;

        ListNode ret = solution.reverseKGroup(ln1, 3);
        for (int i=0; i<5; i++) {
            System.out.printf("ret:%d\n", ret.val);
            ret = ret.next;
        }

        System.out.println();

    }

}