# Arrange consonants and vowels nodes in a linked list ### Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of a linked list can be a huge plus point in coding interviews.

### Problem Statement

In this problem, we will be given a linked list in which each node will have an alphabet character as data, and we need to rearrange the nodes of the linked list so that all nodes having vowel data appear before the consonant ones.

Note: We are not allowed to disturb the relative order of vowels and consonants.

Let the given input be: The output should be: ### Problem Statement Understanding

Let’s first understand the problem statement with the help of examples.

If the given linked list is c→a→l→e→p→o→w:

• Then, according to the problem statement, we need to rearrange the node of the linked list such that all the vowel nodes come before the consonant nodes. Also, we need to make sure that the order of occurrence of nodes within vowel nodes and consonant nodes after rearrangement should be the same as their order of occurrence in the original list.
• The output linked list after rearrangement of nodes will be a→e→o→c→l→p→w.
• In the output linked list, we can see that all the vowel nodes a, e, o are before the consonant nodes c, l, p and w. Also, if we notice carefully, we can observe that within vowel nodes and consonant nodes the order of occurrences of nodes is the same as their order of occurrence in the input list.
• The order of occurrence of vowel nodes in the input list is a, e, o and similarly in our output list, the order of occurrence of vowel nodes is the same a, e, o.
• The order of occurrence of consonant nodes in the input list is c, l, p, w and similarly in our output list the order of occurrence of consonant nodes is the same c, l, p, w.

Let’s take another example, say if the input list is: a→b→c→d→e→o→i→u

• In this case, our output singly linked list after rearrangement will be: a→e→o→i→u→b→c→d

Now, I think the problem statement is clear, so let's see how we can approach it. Any ideas?

• The naive approach would be to create 2 vectors that would be storing the address of nodes. While traversing the list, insert vowel nodes in the first vector and consonant ones in the second one. Finally, create a new linked list, keeping all vowel nodes before consonant nodes.

The above approach will have a linear space and time complexity. But can we do better than this? Yes, we can improve the space complexity of our code to constant space.

• So, our idea will be to traverse the list and find the first vowel node. This will be the new head of our modified list. Now, we would bring this node at the beginning of the list and make this head of our modified list. We would store the previous vowel node’s address, and when we encounter another vowel node in the future, we would remove it from there and place it after this node. We will repeat this process till we traverse the whole list completely.

Let’s move to the next section to see this process in more depth.

### Approach and Algorithm

1) Find the first vowel node and make it head of the list, i.e., bring it before the old head of the list.
2) Now store the position of the previous vowel node.
3) Traverse the list, and when we encounter a vowel node,
a) We would remove it from its place.
b) Insert it after the previous vowel node.
c) Update the previous vowel variable to this node.
d) Connect it with the remaining list.
4) At last, the consonants would automatically come after vowels and the order of occurrence of each vowel and consonant would be preserved.

### Dry Run

For better understanding follow dry run along with code   ### Code Implementation

```#include
using namespace std;
class Node
{
public:
char data;
Node* next;
Node(char x){
data = x;
next = NULL;
}
};

}
cout<<'\n';
}

bool isVowel(char x)
{
if(x == 'a' || x == 'e' || x == 'i' ||x == 'o' || x == 'u')
return true;

return false;
}

{

// to keep track of previously encountered vowel
Node *prevVowel;

// empty list
return NULL;

//To find first vowel node, run a loop separately
//as this would be head of our newly created list

else
{

while (curr->next != NULL &&!isVowel(curr->next->data))
curr = curr->next;

//when there are only consonants in the list.
if (curr->next == NULL)

//found the head of new list so update prevVowel, remove
//it form its place and make it head of new list
curr->next = curr->next->next;
}

// Now traverse the list and perform the operations
// mentioned in step 3

while (curr != NULL && curr->next != NULL)
{
if (isVowel(curr->next->data))
{

if (curr == prevVowel)
{
// if current node is just after prevVowel
prevVowel = curr = curr->next;
}
else
{

Node *temp = prevVowel->next;

// move current node after prevVowel
prevVowel->next = curr->next;

// update prevVowel
prevVowel = prevVowel->next;

curr->next = curr->next->next;

// re-attach the prevVowel with remaining list
prevVowel->next = temp;
}
}
else
{

// if no vowel is present then simply move to next
curr = curr->next;
}
}
}

int main()
{

printf("Input list:\n");

printf("Output list:\n");

return 0;
}
```
```#include
#include
#include
/* A linked list node */
struct Node
{
char data;
struct Node *next;
};

/* Function to add new node to the List */
struct Node *newNode(char key)
{
struct Node *temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = key;
temp->next = NULL;
return temp;
}

// utility function to print linked list
{
{
printf("Empty list \n");
return;
}
{
printf("->");
}
printf("\n");
}

// utility function for checking vowel
bool isVowel(char x)
{
return (x == 'a' || x == 'e' || x == 'i' ||
x == 'o' || x == 'u');
}

/* function to arrange consonants and
vowels nodes */
{

// for keep track of vowel
struct Node *latestVowel;

// list is empty
return NULL;

else
{
while (curr->next != NULL &&
!isVowel(curr->next->data))
curr = curr->next;

if (curr->next == NULL)
curr->next = curr->next->next;
}

while (curr != NULL && curr->next != NULL)
{
if (isVowel(curr->next->data))
{
if (curr == latestVowel)
{
latestVowel = curr = curr->next;
}
else
{
struct Node *temp = latestVowel->next;

latestVowel->next = curr->next;

latestVowel = latestVowel->next;

curr->next = curr->next->next;
latestVowel->next = temp;
}
}
else
{

curr = curr->next;
}
}
}

int main()
{

printf("Input list :\n");

printf("Output list :\n");

return 0;
}
```
```class Node
{
char data;
Node next;
Node(char x)
{
data=x;
}
}
public class ArrangeVowels
{
{
{
}
System.out.println();
}
static boolean isVowel(char x)
{
if(x== 'a' || x== 'e' || x=='i' || x=='o' || x=='u')
{
return true;
}
return false;
}
{
Node prevVowel;

{
return null;
}
{
}
else{
while(curr.next!=null && !isVowel(curr.next.data))
{
curr=curr.next;
}
if(curr.next==null)
{
}
curr.next=curr.next.next;
}
while(curr!=null && curr.next!=null)
{
if(isVowel(curr.next.data))
{
if(curr==prevVowel)
{
prevVowel=curr=curr.next;
}
else{
Node temp=prevVowel.next;
prevVowel.next=curr.next;
prevVowel=prevVowel.next;
curr.next=curr.next.next;
prevVowel.next=temp;
}
}
else
{
curr=curr.next;
}
}
}
public static void main(String[] args)
{

System.out.println("Input List");

System.out.println("Output List");

}
}
```
```class Node:
def __init__(self, x):
self.data = x
self.next = None

print()

def isVowel(x):
return (x == 'a' or x == 'e' or x == 'i'
or x == 'o' or x == 'u' or x == 'A'
or x == 'E' or x == 'I' or x == 'O'
or x == 'U')

latestVowel = None

return None

else:

while (curr.next != None and
not isVowel(curr.next.data)):
curr = curr.next

if (curr.next == None):

curr.next = curr.next.next

while (curr != None and curr.next != None):
if (isVowel(curr.next.data)):

if (curr == latestVowel):

latestVowel = curr = curr.next

else:

temp = latestVowel.next
latestVowel.next = curr.next
latestVowel = latestVowel.next
curr.next = curr.next.next
latestVowel.next = temp

else:

curr = curr.next

if __name__ == '__main__':

print("Input list:")

print("Output list :")
```

#### Output

Input list:
c, a, l, e, p, o, w,
Output list:
a, e, o, c, l, p, w,

Time Complexity: O(n)
[forminator_quiz id="4874"]

So, in this blog, we have tried to explain how you can arrange consonants and vowels nodes in a linked list in the most optimal way. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

## One thought on “Arrange consonants and vowels nodes in a linked list”

1. patchy says:

This paraցraph will assiѕt the internet people for settіng up new blog or even а bloɡ from start to end.