Given a singly linked list and an integer K, reverses the nodes of the

list K at a time and returns modified linked list.

NOTE : The length of the list is divisible by K
Example :

Given linked list 1 -> 2 -> 3 -> 4 -> 5 -> 6 and K=2,

You should return 2 -> 1 -> 4 -> 3 -> 6 -> 5

Try to solve the problem using constant extra space.

Method:

Reverse k elements at a time

Solution:

Time: O(n)
Space: O(1)

/**
* class ListNode {
*     public int val;
*     public ListNode next;
*     ListNode(int x) { val = x; next = null; }
* }
*/
public class Solution {
// s     e
// 1->2->3->4
// 1<-2<-3->4
// 3->2->1->4

// 3->2->1->4->5->6
//
public ListNode reverse(ListNode start, ListNode end, ListNode previous) {
ListNode n = end.next;
ListNode prev = null;
ListNode p = start;
while (p != n) {
ListNode next = p.next;
p.next = prev;
prev = p;
p = next;
}
start.next = n;
previous.next = prev;
return prev;
}

public ListNode reverseList(ListNode A, int B) {
ListNode start = A;
ListNode end = A;
ListNode dummy = new ListNode(0);
ListNode prev = dummy;
while (end != null) {
for (int i = 1; i < B; i ++) {
end = end.next;
}
ListNode next = end.next;
ListNode newHead = reverse(start, end, prev);
prev = start;
start = next;
end = next;
}
return dummy.next;
}
}

/**
* 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 {
//  (0) 1 2 3 4 5
//   d  c n     e
//  (0) 3 2 1 4 5
//              r
private ListNode reverse(ListNode dummy, ListNode end) {
ListNode curr = dummy.next;
ListNode ret = curr;
ListNode prev = end;
while (curr != end) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
dummy.next = prev;
return ret;
}

public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy.next;
ListNode prev = dummy;
int count = 0;
while (curr != null) {
count ++;
if (count % k == 0) {
prev = reverse(prev, curr.next);
curr = prev.next;
} else {
curr = curr.next;
}
}
return dummy.next;
}
}