## Introduction

As I am writing this at 2 AM, this is going to be a small post but definitely an interesting one. This is mostly asked in interviews and is related to my previous post for Reversing a LinkedList.

## Understanding the problem statement

Given a singly linked list L and a number k, we need to reverse each batch of k elements in the linked list. Here is a pictorial representation for the same.

For the below input linked list and for k equals to 3, you can see the output linked list under it. Each of the triplets are reversed.

## Approach

We need to use our reverse linked list function and instead of running till the end, it should actually run for k nodes. This reverse function must be invoked from a loop which runs till the end of the linked list and in each iteration it processes k nodes.

Here is a pseudo code to understand it better:

##### Understanding the above Pseudo Code

In a given iteration of the outer loop, we invoke the `reverseLL` method which reverses k nodes and returns the head of the reversed and unreversed parts.

The unreversed part is used for the next iteration and the reversed part is attached to the already reversed linked list.
Just to make it more clear here are the three iterations with supporting diagrams.

Iteration 1
We pass the complete linked list in the `reverseLL` method. Post invocation of `reverseLL`, we get the following parts(`headOfReversedLinkedList` and `headOfUnReversedLinkedList` ). The `lastTail` and the `reverseBeginning` variables are null. So we assign the head of reversed linked list to `reverseBeginning`. So, it points to the node containing C.

Also, in the inner while loop we make `lastTail` point to A.

Iteration 2
We pass the unreversed linked list in the `reverseLL` method. Post invocation of `reverseLL`, we get the following parts(`headOfReversedLinkedList` and `headOfUnReversedLinkedList` ). The `lastTail` and the `reverseBeginning` variables are pointing to A and C respectively.

We need to attach A to F and then position `lastTail` to D (positioning the lastTail is always done at the end, in the inner while loop.)

Iteration 3
We pass the unreversed linked list in the `reverseLL` method. Post invocation of `reverseLL`, we get the following parts(`headOfReversedLinkedList` and `headOfUnReversedLinkedList` ). The `lastTail` and the `reverseBeginning` variables are pointing to D and C respectively.

We need to attach D to H and then position `lastTail` to G.

The pointer `reverseBeginning` gives the complete linked list.