Problem of the day
You are given a Singly Linked List of integers and an integer 'K'.
Your task is to modify the linked list by inserting a new node after every 'K' node in the linked list with the node value being equal to the sum of the previous 'K' nodes.
Note :If you reach a situation when the number of nodes remaining in the linked list is less than 'K' but greater than zero, just insert a node with the value equal to the sum of the remaining nodes.
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 never be a list element.
The second line contains a single integer 'K'.
Output Format:
Print the modified linked list.
The elements of the modified list should be single-space separated, terminated by -1.
Note:
You are not required to print the output, it has already been taken care of. Just implement the function.
0 <= L <= 5 * 10^5
-10^3 <= data <= 10^3 and data != -1
1 <= K <= 10^6
where 'L' is the number of nodes in the linked list and 'data' is the value of elements present in the given linked list.
Time Limit: 1 sec
1 2 3 4 5 6 7 -1
3
1 2 3 6 4 5 6 15 7 7 -1
For the given input, K = 3, so we have inserted a node after the first 3 nodes with a value of 6 as (1 + 2 + 3).
Similarly, we insert a node after the next 3 nodes with a value of 15 as (4 + 5 + 6). Now only 1 node is left (with a value 7) and 0 < 1 < K, so we insert a node with the value 7 at the end of the list.
0 6 1 5 -1
2
0 6 6 1 5 6 -1
Try to traverse the linked list doing the insertion operation in the required manner.
O(L), where ‘L’ is the number of nodes in the linked list.
Since we are traversing through the entire list that takes O(L) time and the insertion of a node takes O(1) time. Hence, the overall time complexity is O(L).
O(L / K), ‘L’ is the number of nodes in the linked list and ‘K’ is given as input.
On average, we insert ‘L’ / ‘K’ nodes in the list, thus the overall space complexity is O(L / K).