java - 如何对 LinkedList 的字符串数据进行排序

Question

如何订购包含字符串类型的 LinkedList {a,c,d,b,b,d,c,a,c}。订购后的输出应该是这样的{c,c,c,a,a,d,d,b,b}。复杂度也应该是 O(1*n)。

标签： javaalgorithmsortinglinked-list

Answer 1

我假设组/名称/项目总是四个并且总是c,a和. 在这种假设下很容易：创建四个列表，一个用于项目，一个用于项目，等等。遍历您的链表；对于每个项目，将其附加到相应的新列表中。您可以在琴弦上使用。最后以正确的顺序附加四个新列表。dbcaswitch

这将花费 O(n) 时间和 O(n) 空间。

如果出于某种原因（我不知道它可能是什么）您不想创建四个列表，只需保留对排序列表中应插入 、 和 项目c的a四个位置的四个引用。不过，这将需要决定指向哪里，只要不是所有四个名字都在列表中。db