## Introduction

This blog will discuss the various approaches to solve the **Reverse alternate K nodes in a Singly ****linked list**** **problem. Before jumping into the problem of getting the Reverse alternate K nodes in a Singly Linked List, letâ€™s first understand a Linked list.

A Linked list is a kind of data structure in which the elements are connected using pointers, and each node has the address of the pointer of its next node.

In this Reverse alternate K nodes in a Singly Linked List problem, we need to return the head of the linked list after reversing all the alternate k nodes.

You can refer to this link for more information on the linked list.

__For Example:-__

List :- 10 -> 15 -> 45 -> 17 -> 145 -> 125 -> 5 -> 11 -> 47 -> 43 -> 1 -> 75 , and K = 3

Output :- 45 -> 15 -> 10 -> 17 -> 145 -> 125 -> 47 -> 11 -> 5 -> 43 -> 1 -> 75

Recommended Topic, __Floyds Algorithm__

## Brute Force Approach

Brute Force Solution considers reversing the first â€˜Kâ€™ nodes and iterating the pointer â€˜Kâ€™ indexes forward, and then making a recursive call to reverse the next â€˜Kâ€™ nodes. In this approach, the recursive call will be decided using a boolean variable.

### Algorithm

**Step 1**. Create a function â€˜getResult()â€™ that will accept three parameters, i.e., one head pointer of the linked list, one variable â€˜Kâ€™, and one boolean variable â€˜xâ€™, initially â€˜xâ€™ is true.

**Step 2**. Check if â€˜Xâ€™ is true, then we have to reverse the first â€˜Kâ€™ nodes by calling the recursive function â€˜getResult()â€™.

**Step 3**. Check if â€˜Xâ€™ is false, then we have to iterate our pointer and jump to the node at a distance â€˜Kâ€™ from that node.

**Step 4**. We need to call the recursive function â€˜getResult()â€™ and repeat the process for the remaining nodes and link the resultant list with the tail of the first â€˜Kâ€™ nodes modified initially.

**Step 5.** Return the â€˜headâ€™ of the resultant modified, linked list.

### Implementation in C++

```
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node *next;
Node(int data)
{
this->data = data;
this->next = NULL;
}
};
Node *takeinput()
{
int data;
cin >> data;
Node *head = NULL, *tail = NULL;
while (data != -1)
{
Node *newNode = new Node(data);
if (head == NULL)
{
head = newNode;
tail = newNode;
}
else
{
tail->next = newNode;
tail = newNode;
}
cin >> data;
}
return head;
}
/* Function to print the linked list */
void print(Node *head)
{
Node *temp = head;
while (temp != NULL)
{
cout << temp -> data << " ";
temp = temp -> next;
}
return;
}
Node *getResult(Node *node, int k, bool x)
{
if (node == NULL)
{
return NULL;
}
int count = 1;
Node *prev = NULL;
Node *temp = node;
Node *next = NULL;
while (temp != NULL && count <= k)
{
next = temp -> next;
/* Reverse the nodes only if x is true*/
if (x == true)
{
temp -> next = prev;
}
prev = temp;
temp = next;
count++;
}
if (x == true)
{
node -> next = getResult(temp, k, !x);
return prev;
}
prev -> next = getResult(temp, k, !x);
return node;
}
Node *reverse(Node *head, int k)
{
return getResult(head, k, true);
}
int main()
{
Node *head = takeinput();
cout << "Given Linked List:- " ;
print(head);
cout << endl;
int k = 3;
head = reverse(head, k);
cout << "Modified Linked List:- " ;
print(head);
}
```

Output :

```
Given Linked List:- 10 -> 15 -> 45 -> 17 -> 145 -> 125 -> 5 -> 11 -> 47 -> 43 -> 1 -> 75
Modified Linked List:- 45 -> 15 -> 10 -> 17 -> 145 -> 125 -> 47 -> 11 ->
```

#### Complexity Analysis

**Time Complexity: **O(N)

Incall to â€˜getResult()â€™, we are working on â€˜Kâ€™ nodes at one time, either it is the job of reversing the nodes or just traversing them, and in total, we are working on â€˜â€™ nodes, therefore, the overall time complexity is O(N).

**Space Complexity: **O(N)

As we are using a linked list of size â€˜Nâ€™, therefore, the overall space complexity will be O(N).