Sorting a single linked list
This problem is pretty popular in coding interviews. You are given a set of unsorted integers represented as a single linked list and you need to sort them. Sounds pretty straightforward. But no! Best solution to this problem depends on what user wants. Time efficient solution to sort numbers is always in O(nlgn). One can use the likes of merge-sort or quick-sort here, even for single linked list. Solutions are already explained here. Space efficient solution to sort numbers is always in-place, with some additional pointers and temporary variables. This is important when dealing with data-sets that do not fit in memory. Say sort a billion numbers.
My Code
Define a struct for the single link list node.
A simple insert-at-the-end function for the single link list.
Attempt 1:
Copy the given data (numbers) into a container (data structure) and sort that. I used a C++ vector and in-built sort function that takes O(nlgn).
Attempt 2:
Use additional pointers to keep track of current maximum while looping thru the given single link list and swap data when necessary. In the best case, this will take only O(n) time and practically no extra space. But in the worst case, this will be a O(n2) algorithm. Reason being the helper function, isSorted(), that runs as long as the data is unsorted.
Define a main function to take input(s) for the single link list and check time taken for both the sorts.
Output for small input.
