1

我花了 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
}
4

1 回答 1

1

对 a 进行排序LinkedList是 O(n 2 *log(n))，因为它需要 O(n) 时间来遍历列表以找到一个位置，并且需要 O(n*log(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或扩展某些功能。

于 2013-11-12T23:26:11.580 回答