Sorting a linked list

i have a linked list of words, and i need to sort it alphabetically.
what whould you say the best way to do it?

Two ways come immediately to mind.

1. Sort the actual list. This would involve a swap function that would take two nodes and swap their positions in the list. Of course, you would not be physically moving the nodes, but rather just manipulating the pointers.

2. Create a second index list. Each node in this index list would point to a node in the list you're sorting. Then you sort the index list. An advantage to index lists is that you could create more than one sorting based on different fields as well as to filter out some of the nodes in a kind of query. The parallels with working with databases should be apparent.

3. Create a second sorted list. Read through the original list and insert each node into the new list; you could either create a copy of each node or actually remove it from the original list and insert it into the sorted list -- the latter may be more of what you have in mind. At the end, the original list will no longer exist, so you can simply attach the new list to the original head pointer. It's kind of like adding or removing text from a text file: you open the original file for input and a second file for output, copy the original file to it inserting or deleting what you need to in the process, close the files, delete the original file, and rename the second file to the original's name.

You can use any number of sorting techniques, such as the insertion sort or the bucket sort (separate lists for each initial letter, a-z, each of which you insertion sort, then at the end concatenate the separate lists together; this lessens the search time for the insertion sorts because you're working with shorter lists) or whatever else catches your fancy -- in school, I loved to use sort trees, which is a form of insertion sort but based on a binary search instead of a linear one.

Those are what come immediately to mind off the top of my head. Off-hand, I think that the first may prove rather tricky, the second might not actually do what you want (but keep it in the back of your head for future projects), and the third seems like it would be easier to implement.

Wow, thanks!
that was really helpful.