0% completed
Problem Statement
Given the head of a LinkedList and a number ‘k’, reverse every ‘k’ sized sub-list starting from the head.
If, in the end, you are left with a sub-list with less than ‘k’ elements, reverse it too.
Constraints:
- The number of nodes in the list is n.
1 <= k <= n <= 5000
0 <= Node.val <= 1000
Solution
The problem follows the In-place Reversal of a LinkedList pattern and is quite similar to Reverse a Sub-list
. The only difference is that we have to reverse all the sub-lists. We can use the same approach, starting with the first sub-list (i.e. p=1
, q=k
) and keep reversing all the sublists of size ‘k’.
Code
Most of the code is the same as Reverse a Sub-list
:
Time Complexity
The time complexity of our algorithm will be O(N) where ‘N’ is the total number of nodes in the LinkedList.
Space Complexity
We only used constant space, therefore, the space complexity of our algorithm is O(1).
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible