# Reverse alternate groups of K nodes in a Singly Linked List

#### Algorithms Data Structures linked list Get FREE domain for 1st year and build your brand new site

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)
prev = nullptr
next = nullptr

count = 0
WHILE count < k AND curr
next = curr.next
curr.next = prev
prev = curr
curr = next
count = count + 1

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 *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)

// 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() {

// 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
struct Node *head = new Node(1);
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

// Print list elements
}
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)
prev = nullptr
tail = 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 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

``````

## 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 *prev = nullptr;
Node *tail = 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

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

int main() {

// 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
struct Node *head = new Node(1);
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

// Print list elements
}
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?

O(1)
O(N)
O(N^2)
O(2N)
Space complexity of this algorithm is constant i.e. O(1).

## Question 2

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

O(N logN)
O(logN)
O(N^2)
O(N)
Worst case time complexity of this algorithm is linear i.e. O(N).

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.