# Reverse every K nodes

Question 2. Reverse every k nodes in a linked list. So if the input is A->B->C->D->E->F->G->H and k is 3, then the output should be C->B->A->F->E->D->H->G

Both recursive and non-recursive solutions exist to reverse every k nodes with O(n) time complexity. Although the recursive solution takes more space, we will use it here since it is simpler. If there are n nodes in the linked list, we reverse the first k nodes and then recursively process the remaining n – k nodes. Let the linked list be A->B->C->D->E->F->G->H and k = 3. The diagram below illustrates the technique

## C/C++

```
/*
k: how many nodes should be reversed
Return value: first node of the new linked list after reversing every k nodes
*/
struct node * k_reverse_list(struct node *head, int k)
{
struct node *cur_node,  *prev_node, *temp_node;
int i = 0;

if (!head || k == 0)

prev_node = NULL;

while (cur_node && i < k) {
/*Store the next node in a temporary variable*/
temp_node = cur_node->next;

cur_node->next = prev_node;

/*Update the previous node to the current node */
prev_node = cur_node;

/*Proceed to the next node in the original linked list*/
cur_node = temp_node;

++i;
}

/*
We have reversed k nodes. cur_node points to the (k+1)th node
and head points to the kth node.
Now recursively process the remaining nodes from cur_node onwards
and assign the result to head->next.
*/
if (cur_node)

/*prev_node will point to first node in linked list after reversal*/
return prev_node;
}

```

## Java

```
/*
k: how many nodes should be reversed
Return value: first node of the new linked list after reversing every k nodes
*/
int i = 0;

if (head == null || k == 0)

while (curNode != null && i < k) {
/*Store the next node in a temporary variable*/

curNode.next = prevNode;

/*Update the previous node to the current node */
prevNode = curNode;

/*Proceed to the next node in the original linked list*/
curNode = tempNode;

++i;
}

/*
We have reversed k nodes. So curNode refers to the (k+1)th node.
and head now refers to the kth node.
Now recursively process the remaining nodes from curNode onwards
and assign the result to head.next.
*/
if (curNode != null)

/*prevNode will refer to first node in linked list after reversal*/
return prevNode;
}

```

## Python

```
#k: how many nodes should be reversed
#Return value: first node of the new linked list after reversing every k nodes
@staticmethod
if (not head or k == 0):

prev_node = None
i = 0
while (cur_node and i < k):
#Store the next node in a temporary variable
temp_node = cur_node.next

cur_node.next = prev_node

#Update the previous node to the current node
prev_node = cur_node

#Proceed to the next node in the original linked list
cur_node = temp_node

i += 1

#We have reversed k nodes. So cur_node refers to the (k+1)th node
#and head refers to the kth node.
#Now recursively reverse the remaining nodes from cur_node onwards
#and assign the result to head.next.
if (cur_node):