How about this... ---------------------- Read every node, remove from current linked list, and put it in the new linked list using insertion sort If a node already exists, then increment its value with the value of the node being inserted.
The original linked list is read just once. Insertion sort has a complexity of O(n^2), but going by your problem, there are just 26 characters that are going to be there in the final list. There is no extra space used. ---------------------- If space is not a constraint, then, you can ideally use something like a hash, mapping each node's key to a location on the table, and increment its value. Once the whole of the original list is read, we can re-create the sorted list from the table. This is assuming that the table keeps the keys in some sort of order ---------------------- Just guessing. Looking forward for any better algorithms. -- Arvind --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
