Given a linked list, reverse every group of k nodes. If there is a reminder (a group of less than k nodes) in the end, reverse that last group too.
Input: list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
Output: 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> NULL
Input list consists of two whole groups of three. In the output list the first three and last three nodes are reversed.
Input: list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL
Output: 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 8 -> 7 -> NULL
There are two whole groups of three and one partial group (a remainder that consists of just two nodes). Each of the three groups is reversed in the output.
The function has two parameters: head of the given linked list and k.
Return the head of the linked list after reversing the groups of nodes in it.
● 1 <= number of nodes in the list <= 100000
● -2 * 10^9 <= value stored in any node <= 2 * 10^9
● 1 <= k <= number of nodes
● Cannot use more than constant extra space.
The “constant extra space” constraint rules out using recursion because recursion uses the call stack space (up to O(n) if k=n).
We are forced to use an iterative approach.
iterative_solution.cpp demonstrates how it can be done. The code has comments and is easy to follow.
O(n) because of input and output size.