## 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:

##### Pseudo Code

1 2 |
reverseBatch(node) linkedlisttemp |

##### 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.

## Source Code – Linked List Batch Reversing

To download the complete source please visit github link.

Here is the core method :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
private void reverseBatch(LLNode node, int k){ LLNode nextNode = node; LLNode lastTail = null; LLNode reverseBeginning = null; LLNode temp = null; while (nextNode != null) { ObjectPair pair = reverseLL(node, k); nextNode = pair.first; node = pair.second; if (lastTail != null) { lastTail.next = nextNode; } else { reverseBeginning = nextNode; } temp = nextNode; if (temp != null) { while (temp.next != null) temp = temp.next; lastTail = temp; } } printLL(reverseBeginning); } |

## Analysis

**Running Time : ** The outer loop runs for N/k times where N is the total number of nodes and the inner loop inside the reverseLL method runs for k times. The while loop to position the lastTail runs for k times for each iteration of outer loop. So eventually the running time is k * N/k + k * N/k which is O(N)

**Space Required : **We just use few counters and pointers which is agnostic of the number of nodes in the linked list. Hence it is constant space O(1).

## Conclusion

This can be used for more such reversals, imagine a three way reversal or similar. Look out more such problems.

Don’t forget to **subscribe to TechieMe** to get updates on latest posts.