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_;
}