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

该解决方案需要对列表进行三次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)

1. item 在此伪代码段中,是列表的节点对象- item.data 是其中包含的数据。
2. prepend 和 append 方法。然而,如果不这样做,实施它们应该不会太困难。

你很接近。从3个空列表开始,通过原始列表一次将字符串分发到其中。保留一个指向“a”和“B”列表的最后一个元素(插入的第一个元素)的指针,这样将列表连接在一起就不需要重新转换以找到它们的端点。