Solution to LeetCode Reverse Nodes in k-group question.

Suppose we have a function called `reverse_between(ListNode n, int a, int b)`

which reverses the linked list rooted at `n`

between elements `a`

and `b`

. The question is then reduced to calling `reverse_between`

multiple times. Here is a Java implementation:

public ListNode reverseKGroup (ListNode head, int k) {
if (head == null || k == 1 ) return head;
int len = listLength (head);
if (len < k) return head;
ListNode ret = head;
for (int i = 1 ; i < len - (len % k); i += k){
ret = reverseBetween (ret, i, i+k-1 );
}
return ret;
}
private int listLength (ListNode head){
int len = 0 ;
while (head != null ){
head = head.next ;
len++;
}
return len;
}
public ListNode reverseBetween (ListNode head, int m, int n) {
if (head == null || m == n) return head;
ListNode head_ = head; // save old head
for (int i = 1 ; i < m-1 ; i++) head = head.next ;
ListNode start = head;
ListNode revEnd = m == 1 ? head : head.next ;
ListNode prev = revEnd;
head = prev;
for (int i = m; i <= n; i++){
ListNode next = head.next ;
head.next = prev;
prev = head;
head = next;
}
// Thread appropriately
revEnd.next = head;
if (m == 1 ) head_ = prev; // if we need to replace the head
else start.next = prev;
return head_;
}

Reverse Nodes in k-group