Given a single linked list, and an integer k, we need to reverse the linked list in groups of size k.
For example consider the following diagram of input and output linked lists for k = 3.
There are no tricks involved in the solution for this problem. It is just an implementation challenge where we have to carefully manipulate pointers to achieve the desired result.
Here is the strategy. The first step is to subdivide the list into chunks of size k. The last chunk maybe less than size k (depends on whether the length of the linked list is a multiple of k).
Keep a reference to the beginning of the sub-list, and traverse through k nodes.
Reverse the sub-list and re-arrange the begin and end pointers for the reversed sub-list.
The following diagram might give an overview of the process.
Here is the C++ implementation including recursive as well as iterative implementation.
We can consider the following test cases to test the program.
- An empty/NULL list
- List with just one node
- List with multiple of k size
- List with non-multiple of k size
- Arbitrary list with k = 0, k= 1, k= length(list)
- Any combination of the above.