Write a function named chopBothSides that accepts a reference to a pointer to the front of a linked list, and an integer parameter k, and removes k elements from the front of the list and k elements from the back of the list.
Suppose a variable named front points to the front of a chain storing the following values:
{10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110}
The call of chopBothSides(front, 3); would change the list to store the following elements:
{40, 50, 60, 70, 80}
If we followed this by a second call of chopBothSides(front, 1);, the list would store the following elements:
{50, 60, 70}
If the list is not large enough to remove k elements from each side, do not modify the list and throw an integer exception.
If the list contains exactly 2k elements, it should become empty as a result of the call.
If k is 0 or negative, the list should remain unchanged.
Do not leak memory; if you remove any nodes from the list, free their associated memory.
Constraints:
-
Your code should run in no worse than O(N) time, where N is the length of the list.
(You may make more than one pass over the list, but the number of passes you make can't grow as k or N grow.)
-
Do not use any auxiliary data structures such as arrays, vectors, queues, strings, maps, sets, etc.
-
Do not modify the data field of any nodes; you must solve the problem by changing the links between nodes.
-
You may not construct new
ListNode objects, though you may create as many ListNode* pointers as you like.
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)
};
