Problem of the day
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.
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.
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
1 2 3 4 5 6 7 8 9 10 11 -1
3
2 3 4
2 1 5 4 3 9 8 7 6 10 11 -1
For the given input, the block sizes are 2, 3 and 4 respectively. First, we reverse 2 elements (1->2 becomes 2->1), then the next 3 elements (3->4->5 becomes 5->4->3) and lastly the next 4 elements (6->7->8->9 becomes 9->8->7->6). Thus, the final modified list becomes 2->1->5->4->3->9->8->7->6->10->11.
0 6 1 5 -1
2
2 3
6 0 5 1 -1
For the given input, the block sizes are 2 and 3 . First, we reverse 2 elements (0->6 becomes 6->0), then we need to change next 3 elements but we are left with only 2 elements (1->5) and thus it becomes (5->1). Thus, the final modified list becomes 6->0->5->1.
Can you solve this problem by dividing it into subproblems?
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:
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.
O(L), where ‘L’ is the number of nodes in the linked list.
Since we are traversing the entire linked list once, thus the time complexity will be O(L).
O(L / K), where ‘L' is the number of nodes in the linked list and K is the minimum block size from the array ‘B’.
On average, there are L / K recursive calls. Thus, the recursive stack takes O(L / K) space. In the worst case for K = 1, the time complexity will be O(L).