Sorted Insert Into a Linked List

Build a singly linked list that is kept in ascending order the whole time you are filling it.

Read an integer n from standard input, then read n more integers. Insert each value into the list at its correct sorted position as you read it — do not load the values into an array and sort them, and do not sort the list at the end. Equal values may sit in either order.

For the input:

5
8 3 9 1 5

the program prints exactly the output shown in Expected Output.

Format: the first line starts with Sorted:, then for EVERY node a space, the value, a space and ->, and after the last node a space and NULL. The second line is Count:  followed by the number of nodes.

Free the memory you allocate before the program ends — this question checks for memory leaks.