trier une liste chaînée de chaînes par première lettre

Question

Je n'arrive pas à trier une liste chaînée de chaînes avec des chaînes qui commencent toutes par A, B, C. Donc ce serait juste une liste chaînée où toutes les chaînes commençant par 'A' venez avant toutes les chaînes commençant par 'B', et toutes ces chaînes viennent avant toutes les chaînes commençant par 'C.' La liste n'a pas besoin d'être triée plus que ça, et elle n'a pas besoin de conserver les ordres relatifs de les cordes qui commencent par les mêmes lettres. Il doit également être en heure O (N).

La façon dont j'ai pensé à le faire était de créer une liste chaînée vide puis de parcourir la liste chaînée en cherchant toutes les chaînes commençant par A, puis de l'ajouter à la liste vide. Ensuite, parcourez à nouveau la liste donnée pour les chaînes commençant par B, puis ajoutez-la à la liste vide. Je ne suis pas sûr que ce soit O (N) cependant.

Answer 1

Cette solution nécessiterait trois traversées O (N) de la liste, donc elle sera toujours O (N). Le problème avec cela est qu'il crée une nouvelle liste, et les exigences semblent impliquer inplace de tri. Une approche in situ pourrait être d'aller au-dessus de la liste et de déplacer tout élément commençant par A au début et tout élément commençant par C jusqu'à la fin. .: par exemple

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) 

Notes:

1. item dans cet extrait de pseudo-code est l'objet de nœud de la liste - item.data est les données qu'il contient. Cette solution suppose que votre liste a les méthodes prepend et append. Si ce n'est pas le cas, cependant, il ne devrait pas être trop difficile de les mettre en œuvre.

Answer 2

Vous êtes proche. Commencez avec 3 listes vides et distribuez les chaînes dans celles en un seul passage dans la liste originale. Gardez un pointeur vers le dernier élément des listes A et B (les premiers éléments insérés) de sorte que caténer les listes ne nécessite pas de sur-revérification pour trouver leur fin.