Add K Nodes
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.

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 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.

Constraints:

0

Question

Add K Nodes

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.

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 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.

Constraints:

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

Accepted Answer

Naive approach

We will iterate through the linked list and store the sum of the nodes in a variable 'CURR_SUM' (initialized as zero) and keep a check of the number of nodes traversed since the last insertion with a variable 'NODES_TRAVERSED' (also, initialized as zero).
As we traverse the list, we add the value to the 'CURR_SUM' and increment the value of 'NODES_TRAVERSED'.
When the value of 'NODES_TRAVERSED'becomes equal to ‘K’, we insert a node after the current node with its value being equal to 'CURR_SUM'.
Now, we move to the next node in the list, resetting the value of 'CURR_SUM' and 'NODES_TRAVERSED'.
We follow the above steps till we reach the last node of the linked list.
After considering the last node, if the value of ‘NODES_TRAVERSED’ is greater than 0, we insert a node at the end of the list with its value equal to the value of 'CURR_SUM'.

Space Complexity: OtherExplanation:

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).

Time Complexity: O(n)Explanation:

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).