## partitionSort

Author: Marty Stepp (on 2016/06/16)

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;   // nullptr for an empty list
...

public:
};
```
Type your C++ solution code here:

This is a member function problem. Submit a member function that will become part of an existing C++ class. You do not need to write the complete class, just the member function described in the problem.