Write a method that takes a linked list of integers and rearranges the nodes so that the integers stored are sorted into the order of smallest to largest, with the smallest integer in the node at the head of the list. Your method should preserve repetitions of integers. If the original list had any integers occurring more than once, then the changed list will have the same number of each integer. For concreteness you will use lists of integers, but your method should still work if you replace the integer type with any other type for which the less-than operation is defined. Use the following specification:

IntNode listSort(IntNode head)
// Postcondition: The return value is a head
// reference of a linked list with exactly the
// same entries as the original list (including
// repetitions, if any), but the entries
// in this list are sorted from smallest to
// largest. The original linked list is no longer
// available.

Your method will implement the following algorithm (which is often called selection sort): The algorithm removes nodes one at a time from the original list and adds the nodes to a second list until all the nodes have been moved to the second list. The second list will then be sorted.

// Pseudocode for selection sort:
while (the first list still has some nodes)
{
        1. Find the node with the largest element of all the nodes in the first list.
        2. Remove this node from the first list.
        3. Add this node at the head of the second list.
}