## DEV Community

Posted on • Originally published at alkeshghorpade.me

# LeetCode - Reverse Nodes in k-Group

## Problem statement

Given the `head` of a linked list, reverse the nodes of the list `k` at a time, and return the modified list.

`k` is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of `k` then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

Problem statement taken from: https://leetcode.com/problems/reverse-nodes-in-k-group

Example 1:

``````Input: head = [1, 2, 3, 4, 5], k = 2
Output: [2, 1, 4, 3, 5]
``````

Example 2:

``````Input: head = [1, 2, 3, 4, 5], k = 3
Output: [3, 2, 1, 4, 5]
``````

Constraints:

``````- The number of nodes in the list is n.
- 1 <= k <= n <= 5000
- <= Node.val <= 1000
``````

Follow-up: Can you solve the problem in `O(1)` extra memory space?

### Explanation

We can use the standard Reverse linked list code with a slight modification. We pass the count `k` to the method, which reverses the sublist of size `k`. We should keep the track of the next node and the previous node. These are required to point the pointers of the current sublist correctly to our previous sublist.

A C++ snippet of this approach is as follows:

``````ListNode* reverse(ListNode* head, int k) {
return NULL;

ListNode* next = NULL;
ListNode* prev = NULL;
int count = 0;

while (current != NULL && count < k) {
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}

if (next != NULL)

return prev;
}
``````

The time complexity of this approach is O(n). The space complexity is O(n / k). For a linked list of size n, we make `n/k` or `n/k + 1` calls during recursion.

#### Optimized solution: Iterative

We can optimize the space by using the above approach without recursion. We keep track of the previous, current, and next nodes while reversing the linked list in a set of size `k`. Once the sublist of size `k` is reversed we update the previous, current, and next node correctly. We repeat this approach till the list is traversed or the last sublist is less than size `k`.

Let's check the algorithm

#### Algorithm

``````- if !head || k == 1

- set ListNode *temp = new ListNode(1)

- set ListNode *prev, *current, *next = temp
set count = 0
initialize index and i variables

// count the size of the list
- loop while current
- current = current->next
- count++
- while end

- loop while next
- set current = prev->next
- set next = current->next

// if the last sublist is less than size k
// we keep the list as it is.
// Hence setting index = 0.
- index = count > k ? k : 0

- loop for i = 1; i < index; i++
- set current->next = next->next
next->next = prev->next
prev->next = next
next = current->next
- for end

- set prev = current

- update count = count - k
- for end

- return temp->next
``````

The time complexity of the above approach is O(n). The space complexity is O(1).

Let's check our algorithm in C++, Golang, and JavaScript.

#### C++ solution

``````class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if(!head || k == 1) {
}

ListNode *temp = new ListNode(1);

ListNode *prev = temp, *current = temp, *next = temp;

int count = 0, index, i;

while(current) {
current = current->next;
count++;
}

while(next) {
current = prev->next;
next = current->next;

index = count > k ? k : 0;

for(i = 1; i < index; i++) {
current->next = next->next;
next->next = prev->next;
prev->next = next;
next = current->next;
}

prev = current;

count -= k;
}

return temp->next;
}
};
``````

#### Golang solution

``````func reverseKGroup(head *ListNode, k int) *ListNode {
if head == nil || k == 1 {
}

temp := &ListNode{1, nil}

prev, current, next := temp, temp, temp
count, index, i := 0, 0, 0

for current != nil {
current = current.Next
count++
}

for next != nil {
current = prev.Next
next = current.Next

if count > k {
index = k
} else {
index = 0
}

for i = 1; i < index; i++ {
current.Next = next.Next
next.Next = prev.Next
prev.Next = next
next = current.Next
}

prev = current
count -= k
}

return temp.Next
}
``````

#### JavaScript solution

``````var reverseKGroup = function(head, k) {
if(!head || k == 1) {
}

let temp = new ListNode(1, null);

let prev = temp, current = temp, next = temp;
let count = 0, index, i;

while(current) {
current = current.next;
count++;
}

while(next) {
current = prev.next;
next = current.next;

index = count > k ? k : 0;

for(i = 1; i < index; i++) {
current.next = next.next;
next.next = prev.next;
prev.next = next;
next = current.next;
}

prev = current;

count -= k;
}

return temp.next;
};
``````

Let's dry-run our algorithm to see how the solution works.

``````Input: head = [1, 2, 3, 4, 5]
k = 2

Step 1: if !head || k == 1
head -> [1, 2, 3, 4, 5] || 3 == 1
false

Step 2: temp = new ListNode(1)
-> [1]

temp -> [1, 1, 2, 3, 4, 5]
head -> [1, 2, 3, 4, 5]

Step 3: ListNode *prev = temp, *current = temp, *next = temp
count = 0
index, i

Step 4: loop while current
current = current->next
count++

This will count the size of linked list.
count = 5

Step 5: loop while next
current = prev->next
= [1, 2, 3, 4, 5]

next = current->next
= [2, 3, 4, 5]

index = count > k ? k : 0
= 5 > 2 ? 2 : 0
= 2

loop for i = 1; i < 2
1 < 2
true

current->next = next->next
= [3, 4, 5]

next->next = prev->next
= [1, 3, 4, 5]

prev->next = next
= [2, 1, 3, 4, 5]

next = current->next
= [3, 4, 5]

i++
i = 2

loop for i < 2
2 < 2
false

prev = current
= [1, 3, 4, 5]

count = count - k
= 5 - 2
= 3

Step 6: loop while next
next = [3, 4, 5]

current = prev->next
= [3, 4, 5]

next = current->next
= [4, 5]

index = count > k ? k : 0
= 3 > 2 ? 2 : 0
= 2

loop for i = 1; i < 2
1 < 2
true

current->next = next->next
= [3, 5]

next->next = prev->next
= [1, 4, 5]

prev->next = next
= [4, 3, 5]

next = current->next
= [5]

i++
i = 2

loop for i < 2
2 < 2
false

prev = current
= [5]

count = count - k
= 3 - 2
= 1

temp = [2, 1, 4, 3, 5]

Step 7: loop while next
next = [5]

current = prev->next
= [5]

next = current->next
= nil

index = count > k ? k : 0
= 1 > 2 ? 2 : 0
= 0

loop for i = 1; i < 0
1 < 0
false

prev = current
= [5]

count = count - k
= 1 - 2
= -1

Step 8: loop while next
next = nil
false

Step 9: return temp->next
temp = [1, 2, 1, 4, 3, 5]
temp->next = [2, 1, 4, 3, 5]

We return the answer as [2, 1, 4, 3, 5].
``````