Given a singly linked list, the task is to remove the vowels from the given linked list.
Examples:
Input: g -> e -> e -> k -> s -> f -> o -> r -> g -> e -> e -> k -> s
Output: g -> k -> s -> f -> r -> g -> k -> s
Explanation:
After removing vowels {e, e}, {o}, {e, e}. The linked list becomes
g -> k -> s -> f -> r -> g -> k -> sInput: a -> a -> a -> g -> e -> e -> k -> s -> i -> i -> i -> m
Output: g -> k -> s -> m
Explanation:
After removing vowels {a, a, a}, {e, e}, {i, i, i}. The linked list becomes
g -> k -> s -> f -> r -> g -> k -> s
Approach:
There are three cases where we can find the vowels in the given linked list:
- At the starting of the linked list: For removing vowels from the start of the linked list, move the head Node to the first consonant that occurs in the linked list.
For Example:
For Linked List: a -> e -> i -> a -> c -> r -> d -> NULL After moving the head Node from Node a to Node c, We have c -> r -> d -> NULL
- In the between of the linked list: For removing vowels from the between of the linked list, the idea is to keep a marker of the last consonant found in the linked list before the vowel Nodes and change the next link of that Node with the next consonant Node found in the linked list after vowel Nodes.
For Example:
For Linked List:
c -> r -> d -> a -> e -> i -> a -> c -> r -> z -> NULL
last consonant before vowels {a, e, i, a} is d
and next consonant after vowels {a, e, i, a} is r
After linking next pointer of Node d to Node r, We have
c -> r -> d -> r -> z -> NULL
- At the end of the linked list: For removing vowels from the end of the linked list, the idea is to keep a marker of the last consonant found in the linked list before the vowel Nodes and change the next link of that Node with NULL.
For Example:
For Linked List:
c -> r -> d -> a -> e -> i -> a -> NULL
last consonant before vowels {a, e, i, a} is d
After changing the next link of Node to NULL, We have
c -> r -> d -> NULL
Below is the implementation of the above approach:
C++
// C++ program to remove vowels// Nodes in a linked list#include <bits/stdc++.h>using namespace std;// A linked list nodestruct Node { char data; struct Node* next;};// Head Nodestruct Node* head;// Function to add new node to the// ListNode* newNode(char key){ Node* temp = new Node; temp->data = key; temp->next = NULL; return temp;}// Utility function to print the// linked listvoid printlist(Node* head){ if (!head) { cout << "Empty List\n"; return; } while (head != NULL) { cout << head->data << " "; if (head->next) cout << "-> "; head = head->next; } cout << endl;}// Utility function for checking vowelbool isVowel(char x){ return (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u' || x == 'A' || x == 'E' || x == 'I' || x == 'O' || x == 'U');}// Function to remove the vowels Nodevoid removeVowels(){ // Node pointing to head Node struct Node* ptr = head; // Case 1 : Remove the trailing // vowels while (ptr != NULL) { // If current Node is a vowel // node then move the pointer // to next node if (isVowel(ptr->data)) ptr = ptr->next; // Else break if a consonant // node is found else break; } // This prev node used to link // prev consonant to next // consonant after vowels struct Node* prev = ptr; // Head points to the first // consonant of the linked list head = ptr; ptr = ptr->next; // Case 2: If vowels found in // between of the linked list while (ptr != NULL) { // If current node is vowel if (isVowel(ptr->data)) { // Move ptr to the next // node ptr = ptr->next; // Check for vowels // occurring continuously while (ptr != NULL) { // If ptr is a vowel // move to next pointer if (isVowel(ptr->data)) { ptr = ptr->next; } // Else break if // consonant found else break; } // Case 3: If we have ending // vowels then link the prev // consonant to NULL if (ptr == NULL) { prev->next = NULL; break; } // Case 2: change the next // link of prev to current // consonant pointing to // ptr else { prev->next = ptr; } } // Move prev and ptr to next // for next iteration prev = prev->next; ptr = ptr->next; }}// Driver codeint main(){ // Initialise the Linked List head = newNode('a'); head->next = newNode('b'); head->next->next = newNode('c'); head->next->next->next = newNode('e'); head->next->next->next->next = newNode('f'); head->next->next->next->next->next = newNode('g'); head->next->next->next->next->next->next = newNode('i'); head->next->next->next->next->next->next->next = newNode('o'); // Print the given Linked List printf("Linked list before :\n"); printlist(head); removeVowels(); // Print the Linked List after // removing vowels printf("Linked list after :\n"); printlist(head); return 0;} |
Java
// Java program to remove vowels// Nodes in a linked listimport java.io.*;// A linked list nodeclass Node{ char data; Node next; // Function to add new node to the // List Node(char item) { data = item; next = null; }}class GFG{ // Head Node public static Node head; // Utility function to print the // linked list static void printlist(Node head) { if(head == null) { System.out.println("Empty List"); } while(head != null) { System.out.print(head.data + " "); if(head.next != null) { System.out.print("-> "); } head = head.next; } System.out.println(); } // Utility function for checking vowel static boolean isVowel(char x) { return (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u' || x == 'A' || x == 'E' || x == 'I' || x == 'O' || x == 'U'); } // Function to remove the vowels Node static void removeVowels() { // Node pointing to head Node Node ptr = head; // Case 1 : Remove the trailing // vowels while(ptr != null) { // If current Node is a vowel // node then move the pointer // to next node if(isVowel(ptr.data)) { ptr = ptr.next; } // Else break if a consonant // node is found else { break; } } // This prev node used to link // prev consonant to next // consonant after vowels Node prev = ptr; // Head points to the first // consonant of the linked list head = ptr; ptr = ptr.next; // Case 2: If vowels found in // between of the linked list while(ptr != null) { // If current node is vowel if(isVowel(ptr.data)) { // Move ptr to the next // node ptr = ptr.next; // Check for vowels // occurring continuously while(ptr != null) { // If ptr is a vowel // move to next pointer if(isVowel(ptr.data)) { ptr = ptr.next; } // Else break if // consonant found else { break; } } // Case 3: If we have ending // vowels then link the prev // consonant to NULL if(ptr == null) { prev.next = null; break; } // Case 2: change the next // link of prev to current // consonant pointing to // ptr else { prev.next = ptr; } } // Move prev and ptr to next // for next iteration prev = prev.next; ptr = ptr.next; } } // Driver code public static void main (String[] args) { // Initialise the Linked List GFG tree = new GFG(); tree.head = new Node('a'); tree.head.next = new Node('b'); tree.head.next.next = new Node('c'); tree.head.next.next.next = new Node('e'); tree.head.next.next.next.next = new Node('f'); tree.head.next.next.next.next.next = new Node('g'); tree.head.next.next.next.next.next.next = new Node('i'); tree.head.next.next.next.next.next.next.next = new Node('o'); // Print the given Linked List System.out.println("Linked list before :"); printlist(head); removeVowels(); // Print the Linked List after // removing vowels System.out.println("Linked list after :"); printlist(head); }}// This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 program to remove vowels# Nodes in a linked list# A linked list nodeclass Node: def __init__(self, x): self.data = x self.next = None# Head Nodehead = None# Utility function to print the# linked listdef printlist(head): if (not head): print("Empty List") return while (head != None): print(head.data, end = " ") if (head.next): print(end="-> ") head = head.next print()# Utility function for checking voweldef 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')# Function to remove the vowels Nodedef removeVowels(): global head # Node pointing to head Node ptr = head # Case 1 : Remove the trailing # vowels while (ptr != None): # If current Node is a vowel # node then move the pointer # to next node if (isVowel(ptr.data)): ptr = ptr.next # Else break if a consonant # node is found else: break # This prev node used to link # prev consonant to next # consonant after vowels prev = ptr # Head points to the first # consonant of the linked list head = ptr ptr = ptr.next # Case 2: If vowels found in # between of the linked list while (ptr != None): # If current node is vowel if (isVowel(ptr.data)): # Move ptr to the next # node ptr = ptr.next # Check for vowels # occurring continuously while (ptr != None): # If ptr is a vowel # move to next pointer if (isVowel(ptr.data)): ptr = ptr.next # Else break if # consonant found else: break # Case 3: If we have ending # vowels then link the prev # consonant to NULL if (ptr == None): prev.next = None break # Case 2: change the next # link of prev to current # consonant pointing to # ptr else: prev.next = ptr # Move prev and ptr to next # for next iteration prev = prev.next ptr = ptr.next# Driver codeif __name__ == '__main__': # Initialise the Linked List head = Node('a') head.next = Node('b') head.next.next = Node('c') head.next.next.next = Node('e') head.next.next.next.next = Node('f') head.next.next.next.next.next = Node('g') head.next.next.next.next.next.next = Node('i') head.next.next.next.next.next.next.next = Node('o') # Print the given Linked List print("Linked list before :") printlist(head) removeVowels() # Print the Linked List after # removing vowels print("Linked list after :") printlist(head) # This code is contributed by mohit kumar 29 |
C#
// C# program to remove vowels// Nodes in a linked listusing System;// A linked list nodeclass Node{ public char data; public Node next; // Function to add new node to the // List public Node(char item) { data = item; next = null; }}class GFG{ // Head Nodestatic Node head;// Utility function to print the// linked liststatic void printlist(Node head){ if (head == null) { Console.WriteLine("Empty List"); } while (head != null) { Console.Write(head.data + " "); if (head.next != null) { Console.Write("-> "); } head = head.next; } Console.WriteLine();}// Utility function for checking vowelstatic bool isVowel(char x){ return (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u' || x == 'A' || x == 'E' || x == 'I' || x == 'O' || x == 'U');}// Function to remove the vowels Nodestatic void removeVowels(){ // Node pointing to head Node Node ptr = head; // Case 1 : Remove the trailing // vowels while (ptr != null) { // If current Node is a vowel // node then move the pointer // to next node if (isVowel(ptr.data)) { ptr = ptr.next; } // Else break if a consonant // node is found else { break; } } // This prev node used to link // prev consonant to next // consonant after vowels Node prev = ptr; // Head points to the first // consonant of the linked list head = ptr; ptr = ptr.next; // Case 2: If vowels found in // between of the linked list while (ptr != null) { // If current node is vowel if (isVowel(ptr.data)) { // Move ptr to the next // node ptr = ptr.next; // Check for vowels // occurring continuously while (ptr != null) { // If ptr is a vowel // move to next pointer if (isVowel(ptr.data)) { ptr = ptr.next; } // Else break if // consonant found else { break; } } // Case 3: If we have ending // vowels then link the prev // consonant to NULL if (ptr == null) { prev.next = null; break; } // Case 2: change the next // link of prev to current // consonant pointing to // ptr else { prev.next = ptr; } } // Move prev and ptr to next // for next iteration prev = prev.next; ptr = ptr.next; }}// Driver codestatic public void Main(){ // Initialise the Linked List GFG.head = new Node('a'); GFG.head.next = new Node('b'); GFG.head.next.next = new Node('c'); GFG.head.next.next.next = new Node('e'); GFG.head.next.next.next.next = new Node('f'); GFG.head.next.next.next.next.next = new Node('g'); GFG.head.next.next.next.next.next.next = new Node('i'); GFG.head.next.next.next.next.next.next.next = new Node('o'); // Print the given Linked List Console.WriteLine("Linked list before :"); printlist(head); removeVowels(); // Print the Linked List after // removing vowels Console.WriteLine("Linked list after :"); printlist(head);}}// This code is contributed by rag2127 |
Javascript
<script>// javascript program to remove vowels// Nodes in a linked list// A linked list nodeclass Node { // Function to add new node to the // List constructor( item) { this.data = item; this.next = null; }} // Head Node var head; // Utility function to print the // linked list function printlist(head) { if (head == null) { document.write("Empty List"); } while (head != null) { document.write(head.data + " "); if (head.next != null) { document.write("-> "); } head = head.next; } document.write("<br/>"); } // Utility function for checking vowel function isVowel( x) { return (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u' || x == 'A' || x == 'E' || x == 'I' || x == 'O'|| x == 'U'); } // Function to remove the vowels Node function removeVowels() { // Node pointing to head Node var ptr = head; // Case 1 : Remove the trailing // vowels while (ptr != null) { // If current Node is a vowel // node then move the pointer // to next node if (isVowel(ptr.data)) { ptr = ptr.next; } // Else break if a consonant // node is found else { break; } } // This prev node used to link // prev consonant to next // consonant after vowels var prev = ptr; // Head points to the first // consonant of the linked list head = ptr; ptr = ptr.next; // Case 2: If vowels found in // between of the linked list while (ptr != null) { // If current node is vowel if (isVowel(ptr.data)) { // Move ptr to the next // node ptr = ptr.next; // Check for vowels // occurring continuously while (ptr != null) { // If ptr is a vowel // move to next pointer if (isVowel(ptr.data)) { ptr = ptr.next; } // Else break if // consonant found else { break; } } // Case 3: If we have ending // vowels then link the prev // consonant to NULL if (ptr == null) { prev.next = null; break; } // Case 2: change the next // link of prev to current // consonant pointing to // ptr else { prev.next = ptr; } } // Move prev and ptr to next // for next iteration prev = prev.next; ptr = ptr.next; } } // Driver code // Initialise the Linked List head = new Node('a'); head.next = new Node('b'); head.next.next = new Node('c'); head.next.next.next = new Node('e'); head.next.next.next.next = new Node('f'); head.next.next.next.next.next = new Node('g'); head.next.next.next.next.next.next = new Node('i'); head.next.next.next.next.next.next.next = new Node('o'); // Print the given Linked List document.write("Linked list before :<br/>"); printlist(head); removeVowels(); // Print the Linked List after // removing vowels document.write("Linked list after :<br/>"); printlist(head);// This code is contributed by Rajput-Ji </script> |
Output:
Linked list before : a -> b -> c -> e -> f -> g -> i -> o Linked list after : b -> c -> f -> g
Time Complexity: O(N) where N is the number of nodes in the linked list.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
