Linked List Batch Reversing

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.
Linked List Batch Reversing

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

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.
iteration1
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.)
iteration2

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.
iteration3
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 :

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.