在 Java 中按字母顺序对链表进行排序

Question

我花了3个小时搜索并尝试自己制作算法。我想不通，有人可以给我一种按字母顺序对链表进行排序的算法吗？

这是我放弃搜索并决定在这里询问之前尝试的最后一件事

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
}

Answer 1

对

LinkedList进行排序是O（n²*log（n）），因为遍历列表以查找位置和O（n*log（n））排序需要O（n）时间。 因此，最好的办法是将列表转换为数组，对数组进行排序，然后遍历数组并将列表中的节点设置为正确的顺序，即 O（n+n*log（n））。

这正是Collections.sort()所做的（使用合并排序）。您需要做的就是覆盖您的.compareTo()，以便您根据字母顺序进行排序并StringNode实现Comparable<StringNode>。

或者，您可以执行以下操作：

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

注意：
你的myList类必须实现List，或者扩展一些实现的东西。