I am having trouble sorting a linked list of strings with strings that all start with A, B, C. So it would just be a linked list where all strings starting with ‘A’ come before all strings starting with ‘B’, and all of those come before all the strings starting with ‘C.’ The list does not need to be sorted any more than that, and it doesn’t need to preserve the relative orders of the strings that start with the same letters. It also needs to be in O(N) time.
The way I thought of doing it was making an empty linked list and then going through the given linked list looking for all strings that start with A, then add that to the empty list. Then go through the given list again for strings that start with B, then add that to the empty list. I'm not sure if this is O(N) time though.
This solution would require three O(N) traversings of the list, so it will still be O(N). The problem with it is that it creates a new list, and the requirements seem to imply inplace sorting.
An inplace approach could be to go over the list, and move any items starting with A to the beginning and any items starting with C to the end. E.g.:
for item in list:
if item.data[0] == 'A'
item.remove()
list.prepend(item.data)
elif item.data[0] == 'C'
item.remove()
list.append(item.data)
Notes:
item in this pseudocode snippet is the node object of the list - item.data is the data contained in it.prepend and append methods. If it doesn't, though, it shouldn't be too difficult to implement them.