java - 链表的字符串数据如何排序

Question

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

Answer 1

This is for inventory managemant system. There are 4 type dataname a,b,c and d

因此，您需要将其添加到您的帖子中(如果可能，还要解释场景)。

算法

• 既然你说只有 4 种类型的数据，维护 8 个变量 - 节点 a、b、c 的每种数据类型 2 个>,d 如下所示。

Node head_c = null,tail_c = null;
Node head_a = null,tail_a = null;
Node head_d = null,tail_d = null;
Node head_b = null,tail_b = null;

• 现在，遍历链表，每当你得到一个 c 时，就按下面的方式做。

if(head_c == null){
   head_c = current_node;
}else{
   tail_c.next = current_node;
}
tail_c = current_node;

• 对其他节点 a,d,b 也做同样的事情。我们在这里尝试做的基本上是创建 4 个单独的列表 c,a,d,b 分别使用链表的相同(相同hashCode)节点。

• 现在，正如您可能已经理解的那样，对于每个列表，所有要做的就是将一个列表的尾部分配给另一个列表的头部。见下文。

main_head = head_c;
tail_c.next = head_a;
tail_a.next = head_d;
tail_d.next = head_b;
tail_b.next = null;

• 因此，您得到了所需的 c、a、d、b 分组。
• 时间复杂度为O(n)，空间复杂度为O(1)。