Last Updated: 5 Oct, 2020
Reverse Nodes in k-Group
Hard
Asked in companies
You are given a Singly Linked List of integers and an integer array 'B' of size 'N'. Each element in the array 'B' represents a block size. Modify the linked list by reversing the nodes in each block whose sizes are given by the array 'B'.
Note:
1. If you encounter a situation when 'B[i]' is greater than the number of remaining nodes in the list, then simply reverse the remaining nodes as a block and ignore all the block sizes from 'B[i]'.
2. All block sizes are contiguous i.e. suppose that block 'B[i]' ends at a node cur, then the block 'B[i+1]' starts from the node just after the node cur.
Example
Linked list: 1->2->3->4->5
Array B: 3 3 5
Output: 3->2->1->5->4
We reverse the first block of size 3 and then move to block 2. Now, since the number of nodes remaining in the list (2) is less than the block size (3), we reverse the remaining nodes (4 and 5) as a block and ignore all the block sizes that follow.
Input Format:
The first line of the input contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would not be a list element.
The second line contains a single integer 'N', denoting the size of the block array 'B'.
The third line contains 'N' single space-separated elements of the block array 'B'.
Output Format:
You should return the modified linked list where elements should be single-space separated, terminated by -1.
Note:
You don't need to print the output, it has already been taken care of. Just implement the given function.
Constraints:
0 <= L <= 5 * 10^5
-10^9 <= data <= 10^9 and data != -1
1 <= N <= 5 * 10^5
0 <= B[i] <= 5 * 10^5
Where 'L' is the number of nodes in the linked list and 'data' is the value of a node in the linked list.
Time Limit: 1 sec
Approaches
In this approach, we reverse one block at a time and then update the link of that block with the remaining list.
Base case: The list is empty or the entire block array has been considered.
Recursive Rules:
- Recursively reverse the list beginning from k+1 th node (where k is the current block size).
- Reverse the k nodes starting from current head, and connect the new reversed sub-list to the post result.
We can make the next recursive call to reverse the subsequent list, and in the current function, we will do the local reversal and then connect the new reversed list to the post result we obtain from the sub-problem.
Let’s consider the following example :
Linked list: 2->5->7->8->4
Array B: 2 3 4
Initially, we have block size k = 2 and the pointer head points to the node with the value 2. We reverse the first block where k = 2 (2->5 changes to 5->2). After this operation, the head pointer points to the tail of this sublist (sublist becomes 5->2 and head points to node with value 2).
Now, the node next to the tail of this sublist should be the head of the following block after it has been reversed. The next block is 7->8->4, which after reversal becomes 4->8->7. So, the node next to the tail of the sublist 5->2 should be 4, and after updating this link, the list becomes 5->2->4->8->7.
This link is updated using recursion. We just update the value of head->next by calling the same function recursively on the node from which the next block starts. Thus, after reversing first block, we update the link as follows:
head->next = reverse(Node 3 with value 7, block size 3)
This reverses the second block (7->8->4) and updates the link 2->4. Next, we hit the base case as we reach the end of the linked list.
In this approach, we reverse one block at a time while traversing through the list. Let the block size be denoted by K. We need to follow the following steps to reverse the linked list as required :
- Reverse the subsequent K consecutive nodes or the remaining nodes in the list, whichever is smaller. In the meanwhile, keep track of the information of four nodes, the node before head, head, tail, and the node after tail.
- At last, put the reversed sub-list back to the correct position, in between the node before head (former head) and the node after the tail (former tail).
- Move forward to reverse the next sub-list.
Repeat the above steps till we reach the end of the linked list or we have considered the entire block array.