1. Create a new datatype for a singly linked list, that holds integers. Do not re-use any existing linked list datatype from your language.
2. Write a function that merges two sorted linked lists into a single, sorted linked list. This should be done in-place - the input linked lists are mutated into the resulting linked list.
3. Use the merge function from step 2 to produce a full merge-sort algorithm against an arbitrary input linked list. This should also be done in-place.
4. Provide some code to exercise the above sorting function, and verify the results are correct. Test code that checks the result is better than just printing out the list. Ideally, the test cases will print PASS or FAIL.