CodeStepByStep

Write a function named clump that groups together nodes in a linked list that store the same value. Your code should rearrange the linked list so that all occurrences of duplicate values will occur in consecutive order at the site of the first occurrence of that value in the list. For example, you should "clump" all the 4s in the list at the site of the first 4 in the list. The node clumps should remain in the same relative order as in the original list.

Your function accepts two parameters: a reference to a ListNode pointer representing the front of the linked list, and an integer max for the maximum number of values to clump together; any additional occurrences of that same value must be removed (and their memory must be freed). For example, if max is 3 but there are 5 occurrences of the value 10, you should keep only 3 of those 5 occurrences and remove the other 2 occurrences of 10 from the list.

Suppose a ListNode pointer variable named front points to the front of a list storing the following values:

{1, 6, 5, 2, 6, 4, 5, 3, 5, 8, 5, 2, 8, 4, 5, 6, 8, 6}         // original list

After the call of clump(front, 99); , the list should store the following elements:

{1, 6, 6, 6, 6, 5, 5, 5, 5, 5, 2, 2, 4, 4, 3, 8, 8, 8}         // after clump(front, 99);

In the preceding call, the max value passed was very large, so no elements needed to be removed from the list. If the call had instead been clump(front, 2); , the list would instead store the following elements afterward. Notice that the third and fourth occurrence of 6, the third through fifth occurrences of 5, and the third occurrence of 8 were removed.

{1, 6, 6, 5, 5, 2, 2, 4, 4, 3, 8, 8}                           // after clump(front, 2);

Your function should work properly for a list of any size. If the value of max passed is 0 or negative, you should throw an integer exception.

Note that the goal of this problem is to modify the list by modifying pointers. It might be easier to solve it in other ways, such as by changing nodes' data values or by rebuilding an entirely new list, but such tactics are forbidden.

Constraints: Do not modify the data field of any nodes; you must solve the problem by changing links between nodes and adding newly created nodes to the list. Do not use any auxiliary data structures such as arrays, vectors, queues, maps, sets, strings, etc. Do not leak memory; if you remove nodes from the list, free their associated memory. Your code must run in no worse than O(N²) time, where N is the length of the list.

Assume that you are using the ListNode structure as defined below:

struct ListNode {
    int data;         // value stored in each node
    ListNode* next;   // pointer to next node in list (nullptr if none)
}