Reverse List In K Groups

Hard
0/120
Average time to solve is 15m
profile
Contributed by
378 upvotes
Asked in companies
Paytm (One97 Communications Limited)SAP LabsSamsung

Problem statement

You are given a linked list of 'n' nodes and an integer 'k', where 'k' is less than or equal to 'n'.


Your task is to reverse the order of each group of 'k' consecutive nodes, if 'n' is not divisible by 'k', then the last group of nodes should remain unchanged.


For example, if the linked list is 1->2->3->4->5, and 'k' is 3, we have to reverse the first three elements, and leave the last two elements unchanged. Thus, the final linked list being 3->2->1->4->5.


Implement a function that performs this reversal, and returns the head of the modified linked list.


Example: 
Input: 'list' = [1, 2, 3, 4], 'k' = 2

Output: 2 1 4 3

Explanation:
We have to reverse the given list 'k' at a time, which is 2 in this case. So we reverse the first 2 elements then the next 2 elements, giving us 2->1->4->3.


Note: 
All the node values will be distinct.


Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains a single integer 'n', denoting the number of nodes in the linked list.

The second line contains 'n' space-separated integers, denoting the elements of the linked list.

The third line of input contains an integer 'k'.


Output Format: 
Return the head of the modified linked list.


Note: 
You don't need to print anything, just implement the given function. Contents of your returned linked list will be printed in a single line.


Sample Input 1:
6
5 4 3 7 9 2
4


Sample Output 1:
7 3 4 5 9 2


Explanation of the Sample Input 1:
For the given test case, we reverse the nodes in groups of four. But for the last 2 elements, we cannot form a group of four, so leave them as they are. The linked list becomes 7->3->4->5->9->2. Hence the output is 7 3 4 5 9 2


Sample Input 2:
4
4 3 2 8
4


Sample Output 2:
8 2 3 4


Expected Time Complexity:
Try to solve this in O(n).


Expected Space Complexity:
Try to solve this using O(1) extra space.


Constraints:
1 <= n <= 10^4
1 <= k <= n

Time Limit: 1 sec


Hint

Try the simplest possible way.

Approaches (2)
Recursive Approach
  • We can use recursion to solve this problem.
  • The main idea is to reverse the first ‘K’ nodes by ourselves and let the recursive function reverse the rest of the linked list.
  • Let reverseList() be the recursive function which takes the head of the linked list and ‘K’ as the parameters.
  • Now we can iteratively reverse the first ‘K’ nodes of the linked list.
  • And then if we still have some nodes left in the linked list, then we can call reverseList(), until the nodes are exhausted.
Time Complexity

O(N), where ‘N’ is the size of the Linked List.

Space Complexity

O(N), Stack space for recursive calls of ‘N’ nodes of the linked list.

Code Solution
(100% EXP penalty)
Reverse List In K Groups
Full screen
Console