Alphabetically sort a linked list in Java

Question

I've spend 3 hours searching and attempting to make algorithms myself. I can't figure it out, can someone give me an algorithm to Sort a Linked List Alphabetically?

Here is the last thing I attempted before I gave up the search and decided to ask here

class link
{
public void insertNewFirstNode(String value)
{
 StringNode newNode = new StringNode(value, head);
 head = newNode;
 if(tail==null)
 {
 tail=head;
 }
}
public link sort(link L)
{
 link sorted = new link(); 
 StringNode currentNode = head; 
 while (currentNode != null) 
 {
 int data=0;
 if((currentNode.getLink() != null))
 {
 data=currentNode.getData().compareTo(currentNode.getLink().getData());
 if(data==1)
 {
 sorted.insertNewFirstNode(currentNode.getData());
 } 
 currentNode = currentNode.getLink(); 
 }
 else if((currentNode != null))
 { 
 currentNode = currentNode.getLink(); 
 }
 }
 sorted.reverse();
 return sorted;
 }
//Other functions
}

• user2985289: You can provide any other code that solves this problem, you don't have to use this*
• Iłya Bursov: just quick look, you have misprint at if(data==1); - remove last ;

Answer 1

Sorting a LinkedList is O(n²*log(n)), since it takes O(n) time to iterate through the list to find a position and O(n*log(n)) to sort it. So, the best thing to do would be to turn the list into an array, sort the array, and then iterate through the array and set the nodes in the list to their proper order, which is O(n+n*log(n)).

This is exactly what Collections.sort() does (uses merge sort). All you need to do is override your .compareTo() such that you sort based on alphabetical ordering and have StringNode implement Comparable<StringNode>.

Alternatively, you can do something like:

Collections.sort(myList, new Comparator<StringNode>() {
 public int compare(StringNode node1, StringNode node2) {
 return node1.getData().compareTo(node2.getData());
 }
});

NB:
Your myList class must implement List, or extend something that does.