# Shift vowels towards the end of a Single Linked List

We have a linklist which is made of alphabets. We have to shift the vowels towards the end of the linklist, without changing the order in which they appear. So,

A->C->E->F->G->O


should become

C->F->G->A->E->O


This is the code I have written

#include<iostream>

using namespace std;

struct node
{
char ch;
node *next;
};

void enqueue (node **head, node **tail, char val)
{
node *newn = (node *)malloc(sizeof(node));
newn->ch = val;
newn->next = NULL;

{
*tail = newn;
}

(*tail)->next = newn;
(*tail) = newn;

}

{
{
}
cout<<endl;
}

bool isVowel (char ch)
{
ch = ch | 32;

if (ch == 'a' || ch =='e' || ch=='i' || ch=='o' || ch=='u')
return true;
return false;

}

node* segregateVowels (node *head, node *tail)
{

node *fin = tail;

while (temp->next!=fin)
{
cout<<temp->ch<<" "<<fin->ch<<endl;
if (isVowel(temp->next->ch))
{
node *shift = temp->next;
temp->next = temp->next->next;
tail->next = shift;
shift->next = NULL;
tail = shift;
}
else
temp = temp->next;

}

if (temp->next!=NULL && isVowel(temp->next->ch))   /* Handling the case where the last element is a vowel   */
{
node *toMove = temp->next;
temp->next = temp->next->next;
tail->next = toMove;
toMove->next = NULL;

}
else
temp = temp->next;

if (isVowel(head->ch))                  /*  Handling the case where the first element is a vowel    */
{
toMove->next = temp->next;
temp->next = toMove;
}

}

int main()
{
srand(time(NULL));

node  *head = NULL, *tail = NULL;

int i = 20;

while (i>=0)
{
i--;
}

}


Although this does seem to give me correct results, but I have to explicitly check for two edge cases. Also I feel there is a better solution for this problem or a better approach which I seem to be missing. The problem can be handled by creating two separate Link Lists too, and then joining them together. But what modifications do you suggest in the above program?

• Your formatting is really consistent (especially for new lines). Also, can you explain your bit manipulation in isVowel() ? – SylvainD Jul 16 '13 at 14:24
• I don't quite follow what you mean when you say that the formatting is consistent. The bit manipulation in isVowel() is just to turn 'A-Z' to 'a-z'. In case if I ever expand the problem to input both small and capital alphabets. – user2560730 Jul 16 '13 at 14:30
• Ok, thanks, that what I thought. I meant 'inconsistent' as you sometimes skip a few lines for no obvious reasons. – SylvainD Jul 16 '13 at 15:12
• Okay thanks, will keep that in mind. But I think I do that intentionally. I tend to divide my program on modules. Now these are the modules which come to my head when I think upon the implementation of the problem or the algorithm of the problem. So when I give spaces, I segregate those modules. It sometimes helps in debugging, and helps in figuring out if I am making a common mistake over and over again. – user2560730 Jul 16 '13 at 15:27
• @user2560730: This is still C code (you may be using a couple of C++ objects std::cout etc). But the style is C. Note: C++ is a mulch-paradiam language not just OO but there are ways to use the language that avoid the bad parts of C. – Martin York Jul 16 '13 at 23:22

Don't do using namespace std

For loops are here to help you

You could write

int i = 20;
while (i>=0)
{
i--;
}


in a much clearer way using a for-loop : for (int i=20; i>=0; i--) or for (int i=0; i<21; i++). I prefer the latter because I tend to count forward and not backward and it makes much clearer the fact that you want 21 iterations.

Avoid boilerplate and useless code

if (ch == 'a' || ch =='e' || ch=='i' || ch=='o' || ch=='u')
return true;
return false;


could be simply written :

return (ch == 'a' || ch =='e' || ch=='i' || ch=='o' || ch=='u');


Avoid magic numbers

Even if I can guess them, I don't want to learn the ascii code for the different characters. You could rewrite enqueue (&head, &tail, rand()%26+65); in a more explicit way : enqueue (&head, &tail, rand()%26+'A');

Using brackets for single statement is a personal preference but if you do use them for the then-block, then please use them for the else-block as it makes things look "balanced".

Add a bit of documentation I know it's tedious and not so interesting and I usually try to avoid to ask for it but here, I am getting a but confused by the two functions taking two lists as parameters and trying to understand what is intended for both of them.

This being said, I have to go and I'll try to have a deeper look later on.

In the meantime, here's your code with the comments above taken into account :

#include<iostream>

struct node
{
char ch;
node *next;
};

void enqueue (node **head, node **tail, char val)
{
node *newn = (node *)malloc(sizeof(node));
newn->ch = val;
newn->next = NULL;

{
*tail = newn;
}

(*tail)->next = newn;
(*tail) = newn;
}

{
{
}
std::cout<<std::endl;
}

bool isVowel (char ch)
{
ch |= 32; // make it lowercase
return (ch == 'a' || ch =='e' || ch=='i' || ch=='o' || ch=='u');
}

node* segregateVowels (node *head, node *tail)
{

node *fin = tail;

while (temp->next!=fin)
{
std::cout<<temp->ch<<" "<<fin->ch<<std::endl;
if (isVowel(temp->next->ch))
{
node *shift = temp->next;
temp->next = temp->next->next;
tail->next = shift;
shift->next = NULL;
tail = shift;
}
else
{
temp = temp->next;
}
}

if (temp->next!=NULL && isVowel(temp->next->ch))   /* Handling the case where the last element is a vowel   */
{
node *toMove = temp->next;
temp->next = temp->next->next;
tail->next = toMove;
toMove->next = NULL;

}
else
{
temp = temp->next;
}

if (isVowel(head->ch))                  /*  Handling the case where the first element is a vowel    */
{
toMove->next = temp->next;
temp->next = toMove;
}

}

int main()
{
srand(time(NULL));

node  *head = NULL, *tail = NULL;

for (int i=0; i<21; i++)
{
}

}

• I am not really sure which two lists you are talking about. Because there is just one list in the program. Head is pointing to the head of the list and tail is pointing to the tail of the list. – user2560730 Jul 16 '13 at 16:47
• Why do you need two entry points for your list ? This is what is confusing me quite a lot. – SylvainD Jul 16 '13 at 17:22
• Well as I am adding at the end of a link list, I would have to traverse the entire length of the list before adding a new element. But if I save the tail pointer, I could just append at the end of the tail pointer, and update the tail pointer. – user2560730 Jul 16 '13 at 17:39

The main one is that the program fails if there is a vowel at the end but no others (losing the trailing vowel), eg the list Z->Z->A is truncated to Z->Z. This happens (I think) because the code handling the vowel-at-end case assumes that a vowel has already been found - ie. that temp->next->next is not NULL.

In segregateVowels:

• Why the different variable names shift and toMove for things that do the same thing?

• The tail pointer in the caller is not updated.

• I think the if (temp->next!=NULL ... condition is redundant

• only the vowel-at-head case needs to be handled outside the loop, not the vowel-at-end case, for example

node *n = head;
node *last = tail;
while (n != last) {
if (isVowel(n->ch)) {
tail->next = n;
tail = n;
} else {
prev->next = n->next;
}
n = n->next;
tail->next = 0;
} else {
prev = n;
n = n->next;
}
}
if (isVowel(last->ch) && (tail != last)) {
tail->next = last;
} else {
prev->next = last->next;
}
last->next = 0;
tail = last;
}


In this example I have used two pointers to walk through the list, prev (for 'previous') and n. n is no less meaningful than your temp and is shorter. This code fixes the error mentioned above. Note that the (tail != last) could be omitted (ie. it works without) but it is more clearly correct if present.

EDIT - actually if you pass in the size of the list, you can do everything in the loop:

node* segregateVowels (node *head, node *tail, int size)
{

for (int i = 0; (n != NULL) && (i < size); ++i) {
if (isVowel(n->ch)) {
tail->next = n;
tail = n;
} else {
prev->next = n->next;
}
n = n->next;
tail->next = 0;
}
else {
prev = n;
n = n->next;
}
}