The solution given by the author seems to give us the wrong solution. The reason is when a sublist has less then k nodes it still reverses it.
Eg: Given n = 1,2,3,4,5,6,7,8 & k = 3
first we would reverse the first k nodes
n = 3-2-1-4-5-6-7-8
Then we would reverse the nest k nodes
n = 3-2-1-6-5-4-7-8
This should the actual solution, but the answer given by the admin seems to reverse the next 2 nodes as well.
n = 3-2-1-6-5-4-8-7
Instead we should first iterate over the list k nodes and see if there are enough nodes to reverse and then we reverse the first set of nodes. Repeat the process till there are k possible nodes to reverse, if not then add rest of the remaining nodes without reversing them.
Here’s the right code
class ReverseEveryKElements {
public static ListNode reverse(ListNode head, int k) {
if (k < 2 || head == null) {
return head;
}
ListNode curr = head;
ListNode itrHead = head;
ListNode prev = null;
while (itrHead != null) {
int count = 0;
for (int i = 0; i < k && itrHead != null; i++) {
itrHead = itrHead.next;
count++;
}
if (count == k) {
ListNode rev_head = reverseSublist(curr, k);
if (prev == null) {
head = rev_head;
} else {
prev.next = rev_head;
}
prev = curr;
curr = itrHead;
} else {
if (prev != null) {
prev.next = curr;
}
}
}
return head;
}
public static ListNode reverseSublist(ListNode node, int k) {
ListNode curr = node;
ListNode prev = null;
ListNode next = null;
for (int i = 0; i < k && curr != null; i++) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}