MediumAccuracy: 49.98%Submissions: 24K+Points: 4
Done with winning Geekbits? Now win GfG Bag, GfG T-shirt & much more just by writing your experiences. Start Writing, Start Winning.
banner
Given a singly linked list having n nodes containing english alphabets (‘a’-’z’). Rearrange the linked list in such a way that all the vowels come before the consonants while maintaining the order of their arrival. 1:
Input:
n = 9
linked list: a -> b -> c -> d -> e -> f -> g -> h -> i
Output:
a -> e -> i -> b -> c -> d -> f -> g -> h
Explanation:
After rearranging the input linked list according to the condition the resultant linked list will be as shown in output.
Example 2:
Input:
n = 8
linked list: a -> b -> a -> b -> d -> e -> e -> d
Output:
a -> a -> e -> e -> b -> b -> d -> d
Explanation:
After rearranging the input linked list according to the condition the resultant linked list will be as shown in output.
Your Task:
Your task is to complete the function arrangeCV(), which takes head of linked list and arranges the list in such a way that all the vowels come before the consonants while maintaining the order of their arrival and returns the head of the updated linked list.
Expected Time Complexity : O(n)
Expected Auxiliary Space : O(1)
Constraints:
1 <= n <= 104
‘a’ <= elements of linked list <= ‘z’
/*
Structure of node class is:
class Node {
char data;
Node next;
public Node(char data){
this.data = data;
next = null;
}
}
Arrange Consonants and Vowels
MediumAccuracy: 49.98%Submissions: 24K+Points: 4
Done with winning Geekbits? Now win GfG Bag, GfG T-shirt & much more just by writing your experiences. Start Writing, Start Winning.
banner
Given a singly linked list having n nodes containing english alphabets ('a'-'z'). Rearrange the linked list in such a way that all the vowels come before the consonants while maintaining the order of their arrival.
Example 1:
Input:
n = 9
linked list: a -> b -> c -> d -> e -> f -> g -> h -> i
Output:
a -> e -> i -> b -> c -> d -> f -> g -> h
Explanation:
After rearranging the input linked list according to the condition the resultant linked list will be as shown in output.
Example 2:
Input:
n = 8
linked list: a -> b -> a -> b -> d -> e -> e -> d
Output:
a -> a -> e -> e -> b -> b -> d -> d
Explanation:
After rearranging the input linked list according to the condition the resultant linked list will be as shown in output.
Your Task:
Your task is to complete the function arrangeCV(), which takes head of linked list and arranges the list in such a way that all the vowels come before the consonants while maintaining the order of their arrival and returns the head of the updated linked list.
Expected Time Complexity : O(n)
Expected Auxiliary Space : O(1)
Constraints:
1 <= n <= 104
'a' <= elements of linked list <= 'z'
*/
class Solution {
/*Time : O(n) space : O(1)*/
public Node arrangeCV(Node head){
//write code here and return the head of changed linked list
Set<Character> hset=new HashSet<>(List.of('a','e','i','o','u'));
Node curr=head, vovles=new Node('0'), v=vovles, consonents=new Node('0'), c=consonents;
while(curr!=null){
if(hset.contains(curr.data)){
//add to voles list
v.next=curr;
v=v.next;
}else{
//add to consonents list
c.next=curr;
c=c.next;
}
curr=curr.next;
}
//remove the first dummy node
vovles=vovles.next;
consonents=consonents.next;
//put the last element pointer to null to avoid cycles
c.next=null;
v.next = consonents;
//return the new list the head will begin with vovles
return vovles==null ? consonents : vovles;
}
}
