We also often sort data structures in order to organize the values stored in them. In this exercise, you will sort a linked list from smallest value to largest value.
To sort a linked list, we can do the following:
- Instantiate a new linked list
- Find the maximum value of our inputted linked list
- Insert the maximum to the beginning of the new linked list
- Remove the maximum value from the inputted linked list
- Repeat steps 2-4 until the head node of the inputted linked list points to
None - Return the new linked list
Instructions
Fill in the sort_linked_list function such that you return a new linked list that is sorted from smallest value to largest value. Step 1 and Step 6 have been completed for you.
Use the methods in linkedlist.py and node.py to traverse, remove, and get values from the list.
Test cases have been provided for you in order to test your code.
Using the steps described in the narrative to write your sort function, what would be the big O runtime of the function? We will learn how to sort data structures with faster runtimes in future courses.
Scroll to the bottom of the code and change the value of runtime to whichever one of these values you think the big O runtime of sort_linked_list is:
"1""N""log N""N log N""N^2""2^N""N!"