Objective:

– Use fundamental data structures such as stacks, queues, linked-lists, and trees to represent data and meet application requirements.

– Demonstrate knowledge of recursion by describing common applications and by effectively using it to solve problems.

– Use appropriate algorithms to solve common computing problems.

Problem:

In this problem, you will rearrange the nodes in a linked-list from the smallest integer to the largest integer (i.e., the head node should hold the smallest integer in the list). Implement a method called listSort() that receives a value head that points to the first node of the unsorted linked-list. The method then returns a value head which is a reference to the sorted list. The method signature should use the following specification:

IntNode listSort(IntNode head)

For simplicity, your method will use the selection sort algorithm to sort the linked-list.

NOTE:

1. Implement the linked-list application as demonstrated in the lecture video. Therefore, you should submit a complete, stand-alone, runnable program.

2. Your method should be implemented such that it moves an entire node from the unsorted linked-list to the sorted linked-list. Therefore, the unsorted list should reduce in size as the sorted list increases in size. This method should NOT create new nodes.

3. At the end of the operations, the sorted list should have the same number of nodes as the unsorted list initially had.