按第一个字母对字符串的链接列表进行排序

Question

我在对所有以 A、B、C 开头的字符串的链接列表进行排序时遇到问题。所以它只是一个链接列表，其中所有以“A”开头的字符串都在所有以“开头的字符串之前” B'，所有这些都在所有以 'C' 开头的字符串之前。该列表不需要再排序，也不需要保留以相同开头的字符串的相对顺序字母。它也需要在 O(N) 时间内。

我想到的方法是创建一个空链表，然后遍历给定链表以查找所有以 A 开头的字符串，然后将其添加到空链表中。然后再次遍历给定列表以查找以 B 开头的字符串，然后将其添加到空列表中。不过我不确定这是否是 O(N) 时间。

Answer 1

此解决方案需要对列表进行三次 O(N) 遍历，因此它仍然是 O(N)。它的问题是它创建了一个新列表，并且要求似乎暗示就地排序。

一种就地方法可能是遍历列表，将所有以 A 开头的项目移到开头，将所有以 C 开头的项目移到结尾。例如：

for item in list:
    if item.data[0] == 'A'
        item.remove()
        list.prepend(item.data)
    elif item.data[0] == 'C'
        item.remove()
        list.append(item.data)

备注：

item在此伪代码片段中是列表的节点对象 - item.data是其中包含的数据。
此解决方案假定您的列表具有 prepend 和 append 方法。但是，如果没有，实施它们应该不会太困难。

Answer 2

你很接近。从 3 个空列表开始，通过原始列表一次性将字符串分配到这些列表中。保留指向 'A 和 'B' 列表（插入的第一个元素）的最后一个元素的指针，以便将列表连接在一起不需要遍历即可找到它们的末端。

按第一个字母对字符串的链接列表进行排序

sorting a linked list of strings by first letter

runtime

linked-list

pseudocode