Write a Java method of the LinkedIntList class called removeAlternating that removes a node from each pair of nodes in a list in an alternating fashion. In the first pair, the first number should be removed. In the second pair, the second number should be removed. In the third pair, it goes back to the first number being removed. This pattern repeats for pairs that follow. If the list has odd length, the last value should never be removed since it is not part of a pair. The values removed from the list should be returned in a new LinkedIntList with the values appearing the same order as the original list.

For example, if we had a variable list1 that stores the values: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

After the following method call: LinkedIntList list2 = list1.removeAlternating();

list1 and list2 would store the following values:

list1: [2, 3, 6, 7, 10, 11]

list2: [1, 4, 5, 8, 9]

Notice that list2 stores the first values from pairs pair1, pair3, and pair5 and the second values from pairs pair2 and pair4 from the original list that were removed while all of the other values remained in list1. Notice that the number 11 was not removed from the list because it does not belong to a pair.

Your solution should follow the following restrictions:

You may define private helper methods to solve this problem, but otherwise you may not assume that any particular methods are available.

You are allowed to define your own variables of type ListNode, but you may not construct any new nodes.

You may not use any auxiliary data structure to solve this problem (no array, ArrayList, Stack, Queue, String, etc).

You also may not change any data fields of the nodes. You MUST solve this problem by rearranging the links of the lists.

Your solution must run in O(n) time where n is the length of the original list.