Append Nodes for coding interview round

New update is available. Click here to update.

Last Updated: 5 Oct, 2020

Append Nodes

Moderate

Solve now

Problem statement

You have been given an integer Linked List.

After every 'M' nodes, you have to take the sum of the next 'N' nodes and append that sum to the linked list. Do this till the end of the Linked List.

Note:

You just need to return the head of the new linked list.

In case the linked list ends after adding K nodes, where K is any positive integer less than 'N'.Append the sum of those K nodes at the end of the linked list.

Input Format:

The first line of input contains an integer 'T' representing the number of Test cases.
The next 2 * 'T' lines denote the T test cases. Each test case consists of two lines.

The first line of each test case contains the elements of the Linked list separated by space and the linked list is terminated by -1.

The second line of each test case contains two integers separated by a single space denoting 'N' and 'M' respectively, where in the linked list, after every 'M' nodes, take the sum of the next 'N' nodes and append that sum to the linked list.

Output Format:

For each test case, return the modified linked list with elements separated by space.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10        
1 <= n <= 10^4
1 <= N <= 10^4
1 <= M <= 10^4
-10^5 <= VAL <= 10^5

Where 'n' denotes the length of the linked list and 'VAL' represents a node value of the linked list.

Time limit: 1 sec

Solve now

Approaches

01Approach

Initially maintain two variables, ‘COUNTM’ and ‘COUNTN’ and Initialize them to ‘0’, where ‘COUNTM’ will keep track of iterating ‘M’ nodes which are to be skipped and ‘COUNTN’ will keep track of iterating ‘N’ nodes whose sum needs to be calculated. Also, maintain a boolean variable ‘TURNN’ representing which variable to count on, ‘N’ or ‘M’. If the ‘TURNN’ variable is ‘TRUE’ we would increment on ‘COUNTN’ else ‘COUNTM’. Set ‘TURNN’ to false because initially, we would increment ‘COUNTM’ as we need to skip the first ‘M’ nodes of the linked list.

Create a helper function with the help of which we will be recursively traversing through the linked list and pass all the required variables to the helper function as displayed in the code. After ‘M’ recursive calls, ’COUNTM’ would be equal to ‘M’, thereby which we will set ‘COUNTM’ to ‘0’, ‘TURNN’ to ‘TRUE’, and start incrementing ‘COUNTN’. If ‘COUNTN’ reaches ‘N’, append the sum of those ‘N’ nodes to the linked list. The base condition of the recursive helper function would be when we encounter the node’s next is ‘NULL’. Here if ‘TURNN’ is ‘FALSE’, we would simply return ‘HEAD’, otherwise, we would append the temporary sum to the end of the linked list and then return the ‘HEAD’.

Solve now

02Approach

Initially maintain two variables, ‘COUNTM’ and ‘COUNTN’ and Initialize them to ‘0’, where ‘COUNTM’ will keep track of iterating ‘M’ nodes which are to be skipped and ‘COUNTN’ will keep track of iterating ‘N’ nodes whose sum needs to be calculated. Also, maintain a boolean variable ‘TURNN’ representing which variable to count on, ‘N’ or ‘M’. If ‘TURNN’ variable is ‘TRUE’ we would increment on ‘COUNTN’ else ‘COUNTM’. Set ‘TURNN’ to ‘FALSE’ because initially, we would increment ‘COUNTM’ as we need to skip first ‘M’ nodes of the linked list.

As soon as ‘COUNTM’ is equal to ‘M’, set ‘TURNN’ to ‘TRUE’ and set ‘COUNTM’ again to ‘0’. Now keep a temporary variable to hold the sum of next ‘N’ nodes, and keep increasing ‘COUNTN’, and as soon as ‘COUNTN’ reaches ‘N’, append the sum contained in a temporary variable to the linked list, set ‘COUNTN’ to ‘0’ and ‘TURNN’ again to ‘FALSE’. Keep repeating this process until we reach the end of the linked list. If we reach the end of the linked list before ‘COUNTM’ reaches ‘M’, there will be no changes in our answer, but if we reach the end before ‘COUNTN’ reaches ‘N', then append the sum contained in the temporary variable to end of the linked list.

Solve now