Arrange consonants and vowels nodes in a linked list
Arrange consonants and vowels nodes in a linked list
In this problem, we have given a singly linked list. Here we will arrange the consonants and vowels nodes of the list so that all the vowel nodes come before the consonants nodes. Also, we will maintain the order of their arrival.
Examples:
Input:
a -> m -> k -> e -> d ->o -> z -> i
Output:
a -> e -> o -> i -> m -> k -> d -> z
Method:
This method will take two array lists and traverse them to find the consonants and vowels. If we found a vowel while traversing, we will store it in the arraylist1; else, we will store it in arraylist2. After this, we will traverse the linked list again, take the data from the array lists, and put it into the linked list for arranging the vowel and consonants.
Source code to arrange consonants and vowels nodes in a linked list using Java programming:
import java.util.*;
public class Arrange
{
// Structure of the node
static class Node
{
char data;
Node next;
public Node(char data)
{
this.data = data;
next = null;
}
}
// For checking the character is vowel or not
static boolean isVowel(char x)
{
return (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u');
}
// For arrange consonants and vowels nodes in a linked list
static void arrangeNodes(Node head)
{
// Arraylist for storing the vowel and consonants
ArrayList<Character> vowel = new ArrayList<>();
ArrayList<Character> consonants = new ArrayList<>();
Node temp = head;
while(temp != null)
{
char t = temp.data;
// For checking for vowel
if(isVowel(t))
{
vowel.add(t);
}
else
{
consonants.add(t);
}
temp = head;
int i = 0;
while(i < vowel.size())
{
temp.data = vowel.get(i);
i++;
temp = temp.next;
}
i = 0;
while(i < consonants.size())
{
temp.data = consonants.get(i);
i++;
temp = temp.next;
}
}
}
/* Method to print nodes in a given linked list */
static void traverse(Node head)
{
while (head != null)
{
System.out.print(head.data + " ");
head = head.next;
}
}
// Driver method
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter the total no of elements");
int t = sc.nextInt();
char a1= sc.next().charAt(0);
Node head= new Node(a1);
Node tail = head;
for (int i = 1; i < t; i++)
{
char a = sc.next().charAt(0);
tail.next = (new Node(a));
tail = tail.next;
}
System.out.println("Linked list before rearranging the nodes :");
traverse(head);
arrangeNodes(head);
System.out.println("\nLinked list after rearranging the nodes:");
traverse(head);
}
}
Output
Time Complexity: The time complexity of the above method is O(n).
Space Complexity: The space complexity of this method is O(n) because we use extra space for storing the vowel and consonants.