Daily bit(e) of C++ | Reverse k-groups in a list
Daily bit(e) of C++ #119, Common interview problem: Reverse k-groups in a singly-linked list.
Today we will look at a common interview problem: Reverse k-groups in a singly-linked list.
Given a singly-linked list and a positive integer k, reverse every consecutive group of k elements. If there are remaining nodes, they should be left in the original order.
You should only modify the order of elements, not their values.
For example, for a list {1,2,3,4,5} and k==2, the output should be {2,1,4,3,5}.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/KPfWc4MKT.
Solution
There isn’t anything algorithmically complex in this problem. However, there are many opportunities to trip up and make a mistake.
Let’s start with the reversal itself. To reverse a list of k elements, we can create a new list of nodes, adding to the front as we iterate.
To call this reversal multiple times, we need to keep track of a couple of things:
the head of the already processed part; this will be our result
the tail of the already processed part; this is where we will link each reversed section as we iterate
the head of the unprocessed part; both for iteration and to link the tail of the processed part
