Get this book -> Problems on Array: For Interviews and Competitive Programming

We are given a pointer to the head of a singly Linked List and you have to write a function to reverse the elements of the given singly Linked List in alternate groups of K nodes. Once the operation is performed, pointer to the head of the Linked List must be returned from the function.

```
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
and
k = 3
Output: 3 -> 2 -> 1 -> 4 -> 5 -> 6 -> 9 -> 8 -> 7 -> 10
```

In the above example, *k* is equal to 3. Therefore we are required to reverse the elements of the linked list in alternate groups of 3 i.e. we reverse first 3 elements `1 â†’ 2 â†’ 3`

to `3 â†’ 2 â†’ 1`

, then keep next 3 elements in same order i.e. `4 â†’ 5 â†’ 6`

and repeat this process for remaining nodes. As a result of the above operation we obtain the linked list having elements `3 â†’ 2 â†’ 1 â†’ 4 â†’ 5 â†’ 6 â†’ 9 â†’ 8 â†’ 7 â†’ 10`

and in that order.

We have explored two approaches:

- Recursive implementation
- Iterative implementation

## Complexity

- Time Complexity:
**O(n)** - Space Complexity:
**O(1)**

# Approach 1: Recursive Implementation

## Algorithm

**Step 1:** Reverse first K elements in the Linked List. While doing that let *curr* be current node, *prev* be previous node of *curr* and *next* be node pointed by *curr->next*.

**Step 2:** Skip reversing next K nodes.

**Step 3:** Now, recursively call *reverseKGroupAltRecursive(curr.next, k)* where *curr.next* points to the (2K+1)-th node and the pointer to resultant list returned by the function is stored in *curr->next* where *curr* currently points to 2K-th node.

**Step 3:** Return *prev* as it now points to the head of resultant list.

## Pseudocode

```
reverseKGroupAltRecursive(head, k)
curr = head
prev = nullptr
next = nullptr
count = 0
WHILE count < k AND curr
next = curr.next
curr.next = prev
prev = curr
curr = next
count = count + 1
IF head
head.next = curr
count = 0
WHILE count < k-1 AND curr
curr = curr.next
count = count + 1
IF curr
curr.next = reverseKGroupAltRecursive(curr.next, k)
return prev
```

## Implementation

Following is the C++ implementation:

```
#include <iostream>
using namespace std;
struct Node {
int val;
struct Node *next;
Node(int x): val(x), next(nullptr) {}
};
Node* reverseKGroupAltRecursive(Node *head, int k) {
struct Node *curr = head;
struct Node *prev = nullptr;
struct Node *next = nullptr;
// Reverse nodes in groups of k
int count = 0;
while(count < k && curr != nullptr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
count++;
}
// Make K-th node (head) point to K+1-th node (curr)
if(head != nullptr)
head->next = curr;
// skip next K-1 nodes
count = 0;
while(count < k-1 && curr != nullptr) {
curr = curr->next;
count++;
}
// Check if the end of linked list is reached
// If not, then make a recursive call to alternatively reverse remaining nodes
if(curr != nullptr)
curr->next = reverseKGroupAltRecursive(curr->next, k);
return prev;
}
int main() {
// Creating singly linked list
// 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
struct Node *head = new Node(1);
struct Node *curr = head;
for(int i=2;i<=8;i++) {
curr->next = new Node(i);
curr = curr->next;
}
// Initialize k
int k = 3;
// Reverse first K nodes of linked list
head = reverseKGroupAltRecursive(head, k);
// Print list elements
while(head) {
cout<<head->val<<" ";
head = head->next;
}
cout<<endl;
return 0;
}
```

## Explanation

- Consider singly linked list where Node pointer
*head*points to first node in`1 â†’ 2 â†’ 3 â†’ 4 â†’ 5 â†’ 6 â†’ 7 â†’ 8`

and let k = 3. - Three Node pointers
*curr*,*prev*and*next*are created having values of*head*, NULL and NULL. - Now, we try to reverse the first K nodes i.e. 3 nodes of the linked list inside the
*while*loop. We loop through the list as long as*count value is less than k*and*curr is not NULL*. - During each iteration each node is reversed and
*prev*points to the reversed linked list i.e. after first iteration*prev*points to`1`

and*next*points to`2 â†’ 3 â†’ 4 â†’ 5 â†’ 6 â†’ 7 â†’ 8`

, after second iteration*prev*points to`2 â†’ 1`

and*next*points to`3 â†’ 4 â†’ 5 â†’ 6 â†’ 7 â†’ 8`

and after third iteration*prev*points to`3 â†’ 2 â†’ 1`

and*next*points to`4 â†’ 5 â†’ 6 â†’ 7 â†’ 8`

after which the loop breaks as count is equal to k. *head*points to the K-th node in reversed linked list i.e.*head*points to 1 in`3 â†’ 2 â†’ 1`

as it's pointer value remains unchanged.- If
*head*is not NULL, make*head.next*point to*curr*where*curr*points to the remaining nodes to be processed in the linked list. This operation joins the tail of reversed linked list to the head of remaining linked list to be processed. - Now we skip the next K nodes using a while loop as we are reversing the linked list in alternative groups of K. We skip until 2K-th node is reached and exit the loop.
*curr*points to 2K-th node. The linked list we have processed so far is`3 â†’ 2 â†’ 1 â†’ 4 â†’ 5 â†’ 6`

and*curr*points to node with value 6. Still`7 â†’ 8`

are yet to be processed. - If
*curr*is not NULL, we make a recursive call to*reverseKGroupAltRecursive*function to alternatively reverse nodes from (2K+1)-th positon which is pointed by the pointer*curr.next*and the above process repeats. The pointer to the alternatively reversed linked list returned from the recursive call is saved to*curr->next*where*curr*points to the 2K-th node in list pointed by*prev*. - Therefore,
*prev*now points to the final list`3 â†’ 2 â†’ 1 â†’ 4 â†’ 5 â†’ 6 â†’ 8 â†’ 7`

- Finally
*prev*pointer is returned.

# Approach 2: Iterative Implementation

## Algorithm

**Step 1:** Reverse first k nodes of the linked list.

**Step 2:** While reversing, we keep track of the first and last node of the reversed linked list using the *join* and *tail* pointer.

**Step 3:** After reversing the k nodes of the linked list, we join the nodes pointed by the *tail* pointer and *join* pointer and make *tail* point to last node of the reversed resultant linked list.

**Step 4:** Skip reversing the next K nodes as the linked list needs to be alternatively reversed.

**Step 4:** We repeat this process until all groups of nodes are alternatively reversed.

## Pseudocode

```
reverseKGroupAltIterative(head, k)
curr = head
prev = nullptr
tail = nullptr
finalHead = nullptr
WHILE curr
join = curr
prev = nullptr
count = 0
WHILE count < k and curr
next = curr.next
curr.next = prev
prev = curr
curr = next
count = count + 1
IF NOT finalHead
finalHead = prev
IF tail
tail.next = prev
tail = join
tail.next = curr
count = 0
WHILE count < k AND curr
prev = curr
curr = curr.next
count = count + 1
tail = prev
return finalHead
```

## Implementation

Following is the C++ implementation:

```
#include <iostream>
using namespace std;
struct Node {
int val;
struct Node *next;
Node(int x): val(x), next(nullptr) {}
};
Node* reverseKGroupAltIterative(Node *head,int k) {
Node *curr = head;
Node *prev = nullptr;
Node *tail = nullptr;
Node *finalHead = nullptr;
while(curr != nullptr) {
// join points to first node in group of k node
// On reversal join points to the last node as order is changed
Node *join = curr;
// Reset the value of prev
prev = nullptr;
int count = 0;
while(count < k && curr != nullptr) {
Node *next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
count++;
}
// finalHead points to main resultant list
if(finalHead == nullptr)
finalHead = prev;
// Join main resultant list and the reversed list
if(tail != nullptr)
tail->next = prev;
// Pointing tail pointer to the new tail node
tail = join;
// Joining the remaining list to be processed with the resultant list
tail->next = curr;
// Next task is to skip next K nodes
count = 0;
while(count < k && curr != nullptr) {
prev = curr;
curr = curr->next;
count++;
}
// Make tail pointer point to the new tail node after skipping K nodes
tail = prev;
}
return finalHead;
}
int main() {
// Creating singly linked list
// 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
struct Node *head = new Node(1);
struct Node *curr = head;
for(int i=2;i<=8;i++) {
curr->next = new Node(i);
curr = curr->next;
}
// Initialize k
int k = 3;
// Reverse first K nodes of linked list
head = reverseKGroupAltIterative(head, k);
// Print list elements
while(head) {
cout<<head->val<<" ";
head = head->next;
}
cout<<endl;
return 0;
}
```

## Explanation

- Consider singly linked list where Node pointer
*head*points to first node in`1 â†’ 2 â†’ 3 â†’ 4 â†’ 5 â†’ 6 â†’ 7 â†’ 8`

and let k = 3. - Four Node pointers
*curr*,*prev*,*tail*and*finalHead*are created having values of*head*, NULL, NULL and NULL. - During, each iteration of outer loop, we set the value of
*join*and*prev*to*curr*and NULL respectively. - Now, we reverse the first K nodes i.e. 3 nodes of the linked list. We loop through the list as long as
*count value is less than k*and*curr is not NULL*. - During each iteration of inner loop, each node is reversed and
*prev*points to the reversed linked list i.e. after first iteration*prev*points to`1`

and*curr*points to`2 â†’ 3 â†’ 4 â†’ 5 â†’ 6 â†’ 7 â†’ 8`

, after second iteration*prev*points to`2 â†’ 1`

and*curr*points to`3 â†’ 4 â†’ 5 â†’ 6 â†’ 7 â†’ 8`

and after third iteration*prev*points to`3 â†’ 2 â†’ 1`

and*curr*points to`4 â†’ 5 â†’ 6 â†’ 7 â†’ 8`

after which the loop breaks as count is equal to k. *finalHead*pointer is used to point to resultant final reversed linked list. For that, during the first iteration of outer loop we point*finalHead*to the reversed list we get`3 â†’ 2 â†’ 1`

. In the successive iterations, we simply append the reversed list obtained at the end of list pointed by*finalHead*i.e. after second iteration of outer loop*finalHead*points to`3 â†’ 2 â†’ 1 â†’ 4 â†’ 5 â†’ 6`

and in the last outer loop iteration*finalHead*points to`3 â†’ 2 â†’ 1 â†’ 4 â†’ 5 â†’ 6 â†’ 8 â†’ 7`

.- Next, if the
*tail*is not NULL, we are setting*tail.next*'s value equal to*prev*and this basically appends the reversed linked list to the reversed resultant linked list pointed by*finalHead*. - Next step is to update value tail pointer by setting it to
*join*pointer value which makes*tail*now point to last node present in resultant linked list.*tail.next*is set to the value of*curr*where*curr*points to the remaining nodes of the linked list to be reversed. - Now we have to skip next K nodes and this is done by using a while loop and we store the previous node in each step using
*prev*. When*curr*points to (2K+1)-th node, we breakout of the loop. Now*tail*pointer's value is set to*prev*where*prev*points to 2K-th node. This becomes the new tail node. - In the end,
*finalHead*points to the final linked list`3 â†’ 2 â†’ 1 â†’ 4 â†’ 5 â†’ 6 â†’ 8 â†’ 7`

. *finalHead*pointer is returned from the function.

## Question 1

#### What is the space complexity of this algorithm?

## Question 2

#### What is the worst case time complexity of this algorithm?

With this article at OpenGenus, you must have the complete idea of algorithm to reverse alternate groups of K nodes in a Singly Linked List. Enjoy.