Write a member function named `partitionSort`

that could be added to the `LinkedIntList`

class.
Your function should assume that the linked list's elements are already sorted by absolute value, and rearrange the list into sorted order.
Suppose a `LinkedList`

variable named `list`

stores the values below.
Notice that the values are in order of absolute value; that is, they would be in sorted order if you ignored the sign of each value.
The call of `list.partitionSort();`

should reorder the values into sorted, non-decreasing order (including sign).

{0, 0, -3, 3, -5, 7, -9, -10, 10, -11, -11, 11, -11, 12, -15} list before call
list after call of
{-15, -11, -11, -11, -10, -9, -5, -3, 0, 0, 3, 7, 10, 11, 12} list.partitionSort();

Because the list is sorted by absolute value, you can solve this problem very efficiently.
Your solution is required to run in O(*N*) time where *N* is the length of the list.
If the list is empty or contains only one element, it should be unchanged by a call to your function.
The behavior of your function is undefined if the initial list is not already sorted by absolute value; you do not need to handle that case.

*Constraints:*
Do not modify the `data`

field of existing nodes.
Do not create any new nodes by calling `new ListNode(...)`

.
You may create as many `ListNode*`

pointers as you like, though.
Do not call any member functions of the `LinkedIntList`

.
For example, do not call `add`

, `remove`

, or `size`

.
You may, of course, refer to the private member variables inside the `LinkedIntList`

.
Note that the list does not have a `size`

or `m_size`

field.
Do not use any auxiliary data structures such as arrays, vectors, queues, maps, sets, strings, etc.
Do not leak memory.
Your code must run in no worse than O(N) time, where N is the length of the list.
Your code must solve the problem by making only a single traversal over the list, not multiple passes.

Write the member function as it would appear in `LinkedIntList.cpp`

.
You do not need to declare the function header that would appear in `LinkedIntList.h`

.
Assume that you are adding this method to the `LinkedIntList`

class as defined below:

class LinkedIntList {
private:
ListNode* front; // NULL for an empty list
...
public:
`your code goes here;`
};