文字列のリンクリストを最初の文字でソート

Question

文字列のリンクリストをA、B、Cで始まる文字列で並べ替えるのに問題があります。 'B'で始まるすべての文字列の前に来て、それらのすべてが 'C'で始まるすべての文字列の前に来ます。リストはそれ以上並べ替える必要はなく、相対順序を保持する必要はありません文字列は同じ文字で始まります。それはまた、O（N）時間内にある必要があります。

空のリンクリストを作成してから、Aで始まるすべての文字列を探して、空のリストに追加しました。その後、Bで始まる文字列についてもう一度指定したリストを調べ、空のリストに追加します。私はこれがO（N）の時間かどうかは分かりません。

Answer 1

この解決策では、リストの3回の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のメソッドがあることを前提としています。しかし、そうでなければ、実装するのは難しいことではありません。

Answer 2

もうすぐです。 3つの空のリストから始めて、元のリストを1回通して文字列を配布します。 'Aと' B 'リスト（挿入された最初の要素）の最後の要素へのポインタを保持して、リストを連結すると、その終わりを見つけるためにリトレバーレスを必要としません。