Given a singly linked list, we need to arrange the consonants and vowel nodes of it in such a way that all the vowels nodes come before the consonants while maintaining the order of their arrival.
Input : a -> b -> c -> e -> d -> o -> x -> i Output : a -> e -> o -> i -> b -> c -> d -> x
The idea is to keep a marker of the latest vowel we found while traversing the list. If we find another vowel, we take it out of the chain and put it after the existing latest vowel. Example: For linked list:
a -> b -> c -> e -> d -> o -> x -> i
say our latestVowel reference references the ‘a’ node, and that we currently reached the ‘e’ node. We do:
a -> e -> b -> c -> d -> o -> x -> i
So what was after the ‘a’ node is now after the ‘e’ node after deleting it, and linking ‘a’ directly to ‘e’.
To properly remove and add links, it’s best to use the node before the one you are checking. So if you have a curr, you will check curr->next node to see if it’s a vowel or not. If it is, we need to add it after the latestVowel node and then it’s easy to remove it from the chain by assigning its next to curr’s next. Also if a list only contains consonants, we simply return head.
Linked list before : a -> b -> c -> e -> d -> o -> x -> i Linked list after : a -> e -> o -> i -> b -> c -> d -> x
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.