Dada una lista unida, necesitamos ordenar las consonantes y los Nodes vocálicos de tal manera que todos los Nodes vocálicos estén antes que las consonantes manteniendo el orden de llegada .
Ejemplos:
Input : a -> b -> c -> e -> d ->
o -> x -> i
Output : a -> e -> o -> i -> b ->
c -> d -> x
Solución :
La idea es mantener un marcador de la última vocal que encontramos mientras recorremos la lista. Si encontramos otra vocal, la sacamos de la string y la ponemos después de la última vocal existente. Ejemplo: Para lista enlazada:
a -> b -> c -> e -> d -> o -> x -> i
digamos que nuestra referencia lastVowel hace referencia al Node ‘a’, y que actualmente llegamos al Node ‘e’. Hacemos:
a -> e -> b -> c -> d -> o -> x -> i
Entonces, lo que estaba después del Node ‘a’ ahora está después del Node ‘e’ después de eliminarlo y vincular ‘a’ directamente a ‘e’.
Para eliminar y agregar enlaces correctamente, es mejor usar el Node antes del que está comprobando. Entonces, si tiene un curr , verificará curr->next node para ver si es una vocal o no. Si es así, debemos agregarlo después del último Node Vowel, y luego es fácil eliminarlo de la string asignando su siguiente al siguiente de curr. Además, si una lista solo contiene consonantes, simplemente devolvemos cabeza.
Implementación:
C
/* C program to arrange consonants and
vowels nodes in a linked list */
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
/* 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
void printlist(struct Node *head)
{
if (! head)
{
printf("Empty list \n");
return;
}
while (head != NULL)
{
printf("%c",head->data);
if (head->next)
printf("->");
head = head->next;
}
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 */
struct Node *arrange(struct Node *head)
{
struct Node *newHead = head;
// for keep track of vowel
struct Node *latestVowel;
struct Node *curr = head;
// list is empty
if (head == NULL)
return NULL;
// We need to discover the first vowel
// in the list. It is going to be the
// returned head, and also the initial
// latestVowel.
if (isVowel(head->data))
// first element is a vowel. It will
// also be the new head and the initial
// latestVowel;
latestVowel = head;
else
{
// First element is not a vowel. Iterate
// through the list until we find a vowel.
// Note that curr points to the element
// *before* the element with the vowel.
while (curr->next != NULL &&
!isVowel(curr->next->data))
curr = curr->next;
// This is an edge case where there are
// only consonants in the list.
if (curr->next == NULL)
return head;
// Set the initial latestVowel and the
// new head to the vowel item that we found.
// Relink the chain of consonants after
// that vowel item:
// old_head_consonant->consonant1->consonant2->
// vowel->rest_of_list becomes
// vowel->old_head_consonant->consonant1->
// consonant2->rest_of_list
latestVowel = newHead = curr->next;
curr->next = curr->next->next;
latestVowel->next = head;
}
// Now traverse the list. Curr is always the item
// *before* the one we are checking, so that we
// can use it to re-link.
while (curr != NULL && curr->next != NULL)
{
if (isVowel(curr->next->data))
{
// The next discovered item is a vowel
if (curr == latestVowel)
{
// If it comes directly after the
// previous vowel, we don't need to
// move items around, just mark the
// new latestVowel and advance curr.
latestVowel = curr = curr->next;
}
else
{
// But if it comes after an intervening
// chain of consonants, we need to chain
// the newly discovered vowel right after
// the old vowel. Curr is not changed as
// after the re-linking it will have a
// new next, that has not been checked yet,
// and we always keep curr at one before
// the next to check.
struct Node *temp = latestVowel->next;
// Chain in new vowel
latestVowel->next = curr->next;
// Advance latestVowel
latestVowel = latestVowel->next;
// Remove found vowel from previous place
curr->next = curr->next->next;
// Re-link chain of consonants after latestVowel
latestVowel->next = temp;
}
}
else
{
// No vowel in the next element, advance curr.
curr = curr->next;
}
}
return newHead;
}
// Driver code
int main()
{
struct Node *head = newNode('a');
head->next = newNode('b');
head->next->next = newNode('c');
head->next->next->next = newNode('e');
head->next->next->next->next = newNode('d');
head->next->next->next->next->next = newNode('o');
head->next->next->next->next->next->next = newNode('x');
head->next->next->next->next->next->next->next = newNode('i');
printf("Linked list before :\n");
printlist(head);
head = arrange(head);
printf("Linked list after :\n");
printlist(head);
return 0;
}
C++
/* C++ program to arrange consonants and
vowels nodes in a linked list */
#include<bits/stdc++.h>
using namespace std;
/* A linked list node */
struct Node
{
char data;
struct Node *next;
};
/* Function to add new node to the List */
Node *newNode(char key)
{
Node *temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
// utility function to print linked list
void 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 vowel
bool isVowel(char x)
{
return (x == 'a' || x == 'e' || x == 'i' ||
x == 'o' || x == 'u');
}
/* function to arrange consonants and
vowels nodes */
Node *arrange(Node *head)
{
Node *newHead = head;
// for keep track of vowel
Node *latestVowel;
Node *curr = head;
// list is empty
if (head == NULL)
return NULL;
// We need to discover the first vowel
// in the list. It is going to be the
// returned head, and also the initial
// latestVowel.
if (isVowel(head->data))
// first element is a vowel. It will
// also be the new head and the initial
// latestVowel;
latestVowel = head;
else
{
// First element is not a vowel. Iterate
// through the list until we find a vowel.
// Note that curr points to the element
// *before* the element with the vowel.
while (curr->next != NULL &&
!isVowel(curr->next->data))
curr = curr->next;
// This is an edge case where there are
// only consonants in the list.
if (curr->next == NULL)
return head;
// Set the initial latestVowel and the
// new head to the vowel item that we found.
// Relink the chain of consonants after
// that vowel item:
// old_head_consonant->consonant1->consonant2->
// vowel->rest_of_list becomes
// vowel->old_head_consonant->consonant1->
// consonant2->rest_of_list
latestVowel = newHead = curr->next;
curr->next = curr->next->next;
latestVowel->next = head;
}
// Now traverse the list. Curr is always the item
// *before* the one we are checking, so that we
// can use it to re-link.
while (curr != NULL && curr->next != NULL)
{
if (isVowel(curr->next->data))
{
// The next discovered item is a vowel
if (curr == latestVowel)
{
// If it comes directly after the
// previous vowel, we don't need to
// move items around, just mark the
// new latestVowel and advance curr.
latestVowel = curr = curr->next;
}
else
{
// But if it comes after an intervening
// chain of consonants, we need to chain
// the newly discovered vowel right after
// the old vowel. Curr is not changed as
// after the re-linking it will have a
// new next, that has not been checked yet,
// and we always keep curr at one before
// the next to check.
Node *temp = latestVowel->next;
// Chain in new vowel
latestVowel->next = curr->next;
// Advance latestVowel
latestVowel = latestVowel->next;
// Remove found vowel from previous place
curr->next = curr->next->next;
// Re-link chain of consonants after latestVowel
latestVowel->next = temp;
}
}
else
{
// No vowel in the next element, advance curr.
curr = curr->next;
}
}
return newHead;
}
// Driver code
int main()
{
Node *head = newNode('a');
head->next = newNode('b');
head->next->next = newNode('c');
head->next->next->next = newNode('e');
head->next->next->next->next = newNode('d');
head->next->next->next->next->next = newNode('o');
head->next->next->next->next->next->next = newNode('x');
head->next->next->next->next->next->next->next = newNode('i');
printf("Linked list before :\n");
printlist(head);
head = arrange(head);
printf("Linked list after :\n");
printlist(head);
return 0;
}
Java
/* Java program to arrange consonants and
vowels nodes in a linked list */
class GfG
{
/* A linked list node */
static class Node
{
char data;
Node next;
}
/* Function to add new node to the List */
static Node newNode(char key)
{
Node temp = new Node();
temp.data = key;
temp.next = null;
return temp;
}
// utility function to print linked list
static void printlist(Node head)
{
if (head == null)
{
System.out.println("Empty List");
return;
}
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');
}
/* function to arrange consonants and
vowels nodes */
static Node arrange(Node head)
{
Node newHead = head;
// for keep track of vowel
Node latestVowel;
Node curr = head;
// list is empty
if (head == null)
return null;
// We need to discover the first vowel
// in the list. It is going to be the
// returned head, and also the initial
// latestVowel.
if (isVowel(head.data) == true)
// first element is a vowel. It will
// also be the new head and the initial
// latestVowel;
latestVowel = head;
else
{
// First element is not a vowel. Iterate
// through the list until we find a vowel.
// Note that curr points to the element
// *before* the element with the vowel.
while (curr.next != null &&
!isVowel(curr.next.data))
curr = curr.next;
// This is an edge case where there are
// only consonants in the list.
if (curr.next == null)
return head;
// Set the initial latestVowel and the
// new head to the vowel item that we found.
// Relink the chain of consonants after
// that vowel item:
// old_head_consonant->consonant1->consonant2->
// vowel->rest_of_list becomes
// vowel->old_head_consonant->consonant1->
// consonant2->rest_of_list
latestVowel = newHead = curr.next;
curr.next = curr.next.next;
latestVowel.next = head;
}
// Now traverse the list. Curr is always the item
// *before* the one we are checking, so that we
// can use it to re-link.
while (curr != null && curr.next != null)
{
if (isVowel(curr.next.data) == true)
{
// The next discovered item is a vowel
if (curr == latestVowel)
{
// If it comes directly after the
// previous vowel, we don't need to
// move items around, just mark the
// new latestVowel and advance curr.
latestVowel = curr = curr.next;
}
else
{
// But if it comes after an intervening
// chain of consonants, we need to chain
// the newly discovered vowel right after
// the old vowel. Curr is not changed as
// after the re-linking it will have a
// new next, that has not been checked yet,
// and we always keep curr at one before
// the next to check.
Node temp = latestVowel.next;
// Chain in new vowel
latestVowel.next = curr.next;
// Advance latestVowel
latestVowel = latestVowel.next;
// Remove found vowel from previous place
curr.next = curr.next.next;
// Re-link chain of consonants after latestVowel
latestVowel.next = temp;
}
}
else
{
// No vowel in the next element, advance curr.
curr = curr.next;
}
}
return newHead;
}
// Driver code
public static void main(String[] args)
{
Node head = newNode('a');
head.next = newNode('b');
head.next.next = newNode('c');
head.next.next.next = newNode('e');
head.next.next.next.next = newNode('d');
head.next.next.next.next.next = newNode('o');
head.next.next.next.next.next.next = newNode('x');
head.next.next.next.next.next.next.next = newNode('i');
System.out.println("Linked list before : ");
printlist(head);
head = arrange(head);
System.out.println("Linked list after :");
printlist(head);
}
}
// This code is contributed by Prerna Saini.
C#
/* C# program to arrange consonants and
vowels nodes in a linked list */
using System;
class GfG
{
/* A linked list node */
public class Node
{
public char data;
public Node next;
}
/* Function to add new node to the List */
static Node newNode(char key)
{
Node temp = new Node();
temp.data = key;
temp.next = null;
return temp;
}
// utility function to print linked list
static void printlist(Node head)
{
if (head == null)
{
Console.WriteLine("Empty List");
return;
}
while (head != null)
{
Console.Write(head.data +" ");
if (head.next != null)
Console.Write("-> ");
head = head.next;
}
Console.WriteLine();
}
// utility function for checking vowel
static bool isVowel(char x)
{
return (x == 'a' || x == 'e' || x == 'i' ||
x == 'o' || x == 'u');
}
/* function to arrange consonants and
vowels nodes */
static Node arrange(Node head)
{
Node newHead = head;
// for keep track of vowel
Node latestVowel;
Node curr = head;
// list is empty
if (head == null)
return null;
// We need to discover the first vowel
// in the list. It is going to be the
// returned head, and also the initial
// latestVowel.
if (isVowel(head.data) == true)
// first element is a vowel. It will
// also be the new head and the initial
// latestVowel;
latestVowel = head;
else
{
// First element is not a vowel. Iterate
// through the list until we find a vowel.
// Note that curr points to the element
// *before* the element with the vowel.
while (curr.next != null &&
!isVowel(curr.next.data))
curr = curr.next;
// This is an edge case where there are
// only consonants in the list.
if (curr.next == null)
return head;
// Set the initial latestVowel and the
// new head to the vowel item that we found.
// Relink the chain of consonants after
// that vowel item:
// old_head_consonant->consonant1->consonant2->
// vowel->rest_of_list becomes
// vowel->old_head_consonant->consonant1->
// consonant2->rest_of_list
latestVowel = newHead = curr.next;
curr.next = curr.next.next;
latestVowel.next = head;
}
// Now traverse the list. Curr is always the item
// *before* the one we are checking, so that we
// can use it to re-link.
while (curr != null && curr.next != null)
{
if (isVowel(curr.next.data) == true)
{
// The next discovered item is a vowel
if (curr == latestVowel)
{
// If it comes directly after the
// previous vowel, we don't need to
// move items around, just mark the
// new latestVowel and advance curr.
latestVowel = curr = curr.next;
}
else
{
// But if it comes after an intervening
// chain of consonants, we need to chain
// the newly discovered vowel right after
// the old vowel. Curr is not changed as
// after the re-linking it will have a
// new next, that has not been checked yet,
// and we always keep curr at one before
// the next to check.
Node temp = latestVowel.next;
// Chain in new vowel
latestVowel.next = curr.next;
// Advance latestVowel
latestVowel = latestVowel.next;
// Remove found vowel from previous place
curr.next = curr.next.next;
// Re-link chain of consonants after latestVowel
latestVowel.next = temp;
}
}
else
{
// No vowel in the next element, advance curr.
curr = curr.next;
}
}
return newHead;
}
// Driver code
public static void Main(String[] args)
{
Node head = newNode('a');
head.next = newNode('b');
head.next.next = newNode('c');
head.next.next.next = newNode('e');
head.next.next.next.next = newNode('d');
head.next.next.next.next.next = newNode('o');
head.next.next.next.next.next.next = newNode('x');
head.next.next.next.next.next.next.next = newNode('i');
Console.WriteLine("Linked list before : ");
printlist(head);
head = arrange(head);
Console.WriteLine("Linked list after :");
printlist(head);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to remove vowels
# Nodes in a linked list
# A linked list node
class Node:
def __init__(self, x):
self.data = x
self.next = None
# Utility function to print the
# linked list
def 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 vowel
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')
#/* function to arrange consonants and
# vowels nodes */
def arrange(head):
newHead = head
# for keep track of vowel
latestVowel = None
curr = head
# list is empty
if (head == None):
return None
# We need to discover the first vowel
# in the list. It is going to be the
# returned head, and also the initial
# latestVowel.
if (isVowel(head.data)):
# first element is a vowel. It will
# also be the new head and the initial
# latestVowel
latestVowel = head
else:
# First element is not a vowel. Iterate
# through the list until we find a vowel.
# Note that curr points to the element
# *before* the element with the vowel.
while (curr.next != None and
not isVowel(curr.next.data)):
curr = curr.next
# This is an edge case where there are
# only consonants in the list.
if (curr.next == None):
return head
# Set the initial latestVowel and the
# new head to the vowel item that we found.
# Relink the chain of consonants after
# that vowel item:
# old_head_consonant.consonant1.consonant2.
# vowel.rest_of_list becomes
# vowel.old_head_consonant.consonant1.
# consonant2.rest_of_list
latestVowel = newHead = curr.next
curr.next = curr.next.next
latestVowel.next = head
# Now traverse the list. Curr is always the item
# *before* the one we are checking, so that we
# can use it to re-link.
while (curr != None and curr.next != None):
if (isVowel(curr.next.data)):
# The next discovered item is a vowel
if (curr == latestVowel):
# If it comes directly after the
# previous vowel, we don't need to
# move items around, just mark the
# new latestVowel and advance curr.
latestVowel = curr = curr.next
else:
# But if it comes after an intervening
# chain of consonants, we need to chain
# the newly discovered vowel right after
# the old vowel. Curr is not changed as
# after the re-linking it will have a
# new next, that has not been checked yet,
# and we always keep curr at one before
# the next to check.
temp = latestVowel.next
# Chain in new vowel
latestVowel.next = curr.next
# Advance latestVowel
latestVowel = latestVowel.next
# Remove found vowel from previous place
curr.next = curr.next.next
# Re-link chain of consonants after latestVowel
latestVowel.next = temp
else:
# No vowel in the next element, advance curr.
curr = curr.next
return newHead
# Driver code
if __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('d')
head.next.next.next.next.next = Node('o')
head.next.next.next.next.next.next = Node('x')
head.next.next.next.next.next.next.next = Node('i')
# Print the given Linked List
print("Linked list before :")
printlist(head)
head = arrange(head)
# Print the Linked List after
# removing vowels
print("Linked list after :")
printlist(head)
# This code is contributed by mohit kumar 29
Javascript
<script>
/* JavaScript program to arrange consonants and
vowels nodes in a linked list */
/* A linked list node */
class Node
{
/* Function to add new node to the List */
constructor(key)
{
this.data=key;
this.next = null;
}
}
// utility function to print linked list
function printlist(head)
{
if (head == null)
{
document.write("Empty List<br>");
return;
}
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');
}
/* function to arrange consonants and
vowels nodes */
function arrange(head)
{
let newHead = head;
// for keep track of vowel
let latestVowel;
let curr = head;
// list is empty
if (head == null)
return null;
// We need to discover the first vowel
// in the list. It is going to be the
// returned head, and also the initial
// latestVowel.
if (isVowel(head.data) == true)
// first element is a vowel. It will
// also be the new head and the initial
// latestVowel;
latestVowel = head;
else
{
// First element is not a vowel. Iterate
// through the list until we find a vowel.
// Note that curr points to the element
// *before* the element with the vowel.
while (curr.next != null &&
!isVowel(curr.next.data))
curr = curr.next;
// This is an edge case where there are
// only consonants in the list.
if (curr.next == null)
return head;
// Set the initial latestVowel and the
// new head to the vowel item that we found.
// Relink the chain of consonants after
// that vowel item:
// old_head_consonant->consonant1->consonant2->
// vowel->rest_of_list becomes
// vowel->old_head_consonant->consonant1->
// consonant2->rest_of_list
latestVowel = newHead = curr.next;
curr.next = curr.next.next;
latestVowel.next = head;
}
// Now traverse the list. Curr is always the item
// *before* the one we are checking, so that we
// can use it to re-link.
while (curr != null && curr.next != null)
{
if (isVowel(curr.next.data) == true)
{
// The next discovered item is a vowel
if (curr == latestVowel)
{
// If it comes directly after the
// previous vowel, we don't need to
// move items around, just mark the
// new latestVowel and advance curr.
latestVowel = curr = curr.next;
}
else
{
// But if it comes after an intervening
// chain of consonants, we need to chain
// the newly discovered vowel right after
// the old vowel. Curr is not changed as
// after the re-linking it will have a
// new next, that has not been checked yet,
// and we always keep curr at one before
// the next to check.
let temp = latestVowel.next;
// Chain in new vowel
latestVowel.next = curr.next;
// Advance latestVowel
latestVowel = latestVowel.next;
// Remove found vowel from previous place
curr.next = curr.next.next;
// Re-link chain of consonants
// after latestVowel
latestVowel.next = temp;
}
}
else
{
// No vowel in the next element, advance curr.
curr = curr.next;
}
}
return newHead;
}
// Driver code
let 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('d');
head.next.next.next.next.next = new Node('o');
head.next.next.next.next.next.next = new Node('x');
head.next.next.next.next.next.next.next = new Node('i');
document.write("Linked list before : <br>");
printlist(head);
head = arrange(head);
document.write("Linked list after :<br>");
printlist(head);
// This code is contributed by unknown2108
</script>
Producción
Linked list before : a->b->c->e->d->o->x->i Linked list after : a->e->o->i->b->c->d->x
COMPLEJIDAD DE TIEMPO:- O(n)
COMPLEJIDAD ESPACIAL:- O(1)
Este artículo es una contribución de Gaurav Miglani . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Otro enfoque:-
Otro enfoque para resolver el problema anterior es crear dos listas enlazadas separadas, una que contenga solo vocales y la otra que contenga solo consonantes.
Recuerde que el siguiente enfoque es fácil de entender PERO REQUIERE UNA COMPLEJIDAD ESPACIAL DE O(N)
Mientras atraviesa la Lista vinculada de entrada dada, si los datos del Node son vocales, agréguelos a la Lista vinculada de vocales y si los datos del Node son consonantes, agréguelos a la Lista vinculada de consonantes.
Después del recorrido, solo tiene que vincular el último Node de vocal al primer Node de consonante de la respectiva Lista Vinculada.
Implementación:
C++
/* C++ program to arrange consonants and
vowels nodes in a linked list */
#include <bits/stdc++.h>
using namespace std;
/* A linked list node */
struct Node {
char data;
struct Node* next;
Node(int x)
{
data = x;
next = NULL;
}
};
/* Function to add new node to the List */
void append(struct Node** headRef, char data)
{
struct Node* new_node = new Node(data);
struct Node* last = *headRef;
if (*headRef == NULL) {
*headRef = new_node;
return;
}
while (last->next != NULL)
last = last->next;
last->next = new_node;
return;
}
// utility function to print linked list
void 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;
}
/* function to arrange consonants and
vowels nodes */
struct Node* arrange(Node* head)
{
Node *vowel = NULL, *consonant = NULL, *start = NULL,
*end = NULL;
while (head != NULL) {
char x = head->data;
// Checking the current node data is vowel or
// not
if (x == 'a' || x == 'e' || x == 'i' || x == 'o'
|| x == 'u') {
if (!vowel) {
vowel = new Node(x);
start = vowel;
}
else {
vowel->next = new Node(x);
vowel = vowel->next;
}
}
else {
if (!consonant) {
consonant = new Node(x);
end = consonant;
}
else {
consonant->next = new Node(x);
consonant = consonant->next;
}
}
head = head->next;
}
// In case when there is no vowel in the incoming LL
// then we have to return the head of the consonant LL
if (start == NULL)
return end;
// Connecting the vowel and consonant LL
vowel->next = end;
return start;
}
// Driver code
int main()
{
struct Node* head = NULL;
append(&head, 'a');
append(&head, 'b');
append(&head, 'c');
append(&head, 'e');
append(&head, 'd');
append(&head, 'o');
append(&head, 'x');
append(&head, 'i');
printf("Linked list before :\n");
printlist(head);
head = arrange(head);
printf("Linked list after :\n");
printlist(head);
return 0;
}
// This code is contributed by Aditya Kumar
Java
/* Java program to arrange consonants and
vowels nodes in a linked list */
import java.util.*;
class GFG{
/* A linked list node */
static class Node {
char data;
Node next;
Node(char x)
{
this.data = x;
this.next = null;
}
};
/* Function to add new node to the List */
static Node append(Node headRef, char data)
{
Node new_node = new Node(data);
Node last = headRef;
if (headRef == null) {
headRef = new_node;
return headRef;
}
while (last.next != null)
last = last.next;
last.next = new_node;
return headRef;
}
// utility function to print linked list
static void printlist(Node head)
{
if (head == null) {
System.out.print("Empty List\n");
return;
}
while (head != null) {
System.out.print(head.data+ " ");
if (head.next!=null)
System.out.print("-> ");
head = head.next;
}
System.out.println();
}
/* function to arrange consonants and
vowels nodes */
@SuppressWarnings("null")
static Node arrange(Node head)
{
Node vowel = null, consonant = null, start = null,
end = null;
while (head != null) {
char x = head.data;
// Checking the current node data is vowel or
// not
if (x == 'a' || x == 'e' || x == 'i' || x == 'o'
|| x == 'u') {
if (vowel==null) {
vowel = new Node(x);
start = vowel;
}
else {
vowel.next = new Node(x);
vowel = vowel.next;
}
}
else {
if (consonant == null) {
consonant = new Node(x);
end = consonant;
}
else {
consonant.next = new Node(x);
consonant = consonant.next;
}
}
head = head.next;
}
// In case when there is no vowel in the incoming LL
// then we have to return the head of the consonant LL
if (start == null)
return end;
// Connecting the vowel and consonant LL
vowel.next = end;
return start;
}
// Driver code
public static void main(String[] args)
{
Node head = null;
head = append(head, 'a');
head = append(head, 'b');
head = append(head, 'c');
head = append(head, 'e');
head = append(head, 'd');
head = append(head, 'o');
head = append(head, 'x');
head = append(head, 'i');
System.out.printf("Linked list before :\n");
printlist(head);
head = arrange(head);
System.out.printf("Linked list after :\n");
printlist(head);
}
}
// This code is contributed by Rajput-Ji
Python3
''' Python program to arrange consonants and
vowels Nodes in a linked list '''
''' A linked list Node '''
class Node:
def __init__(self, data):
self.data = data;
self.next = None;
''' Function to add new Node to the List '''
def append(headRef, data):
new_Node = Node(data);
last = headRef;
if (headRef == None):
headRef = new_Node;
return headRef;
while (last.next != None):
last = last.next;
last.next = new_Node;
return headRef;
# utility function to print linked list
def printlist(head):
if (head == None):
print("Empty List");
return;
while (head != None):
print(head.data, end="");
if (head.next != None):
print("-> ",end="");
head = head.next;
print();
'''
* function to arrange consonants and vowels Nodes
'''
def arrange(head):
vowel = None;
consonant = None;
start = None;
end = None;
while (head != None):
x = head.data;
# Checking the current Node data is vowel or
# not
if (x == 'a' or x == 'e' or x == 'i' or x == 'o' or x == 'u'):
if (vowel == None):
vowel = Node(x);
start = vowel;
else:
vowel.next = Node(x);
vowel = vowel.next;
else:
if (consonant == None):
consonant = Node(x);
end = consonant;
else:
consonant.next = Node(x);
consonant = consonant.next;
head = head.next;
# In case when there is no vowel in the incoming LL
# then we have to return the head of the consonant LL
if (start == None):
return end;
# Connecting the vowel and consonant LL
vowel.next = end;
return start;
# Driver code
if __name__ == '__main__':
head = None;
head = append(head, 'a');
head = append(head, 'b');
head = append(head, 'c');
head = append(head, 'e');
head = append(head, 'd');
head = append(head, 'o');
head = append(head, 'x');
head = append(head, 'i');
print("Linked list before :");
printlist(head);
head = arrange(head);
print("Linked list after :");
printlist(head);
# This code is contributed by Rajput-Ji
C#
/* C# program to arrange consonants and
vowels nodes in a linked list */
using System;
public class GFG {
/* A linked list node */
public class Node {
public char data;
public Node next;
public Node(char x) {
this.data = x;
this.next = null;
}
};
/* Function to add new node to the List */
static Node append(Node headRef, char data) {
Node new_node = new Node(data);
Node last = headRef;
if (headRef == null) {
headRef = new_node;
return headRef;
}
while (last.next != null)
last = last.next;
last.next = new_node;
return headRef;
}
// utility function to print linked list
static void printlist(Node head) {
if (head == null) {
Console.Write("Empty List\n");
return;
}
while (head != null) {
Console.Write(head.data + " ");
if (head.next != null)
Console.Write("-> ");
head = head.next;
}
Console.WriteLine();
}
/*
* function to arrange consonants and vowels nodes
*/
static Node arrange(Node head) {
Node vowel = null, consonant = null, start = null, end = null;
while (head != null) {
char x = head.data;
// Checking the current node data is vowel or
// not
if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u') {
if (vowel == null) {
vowel = new Node(x);
start = vowel;
} else {
vowel.next = new Node(x);
vowel = vowel.next;
}
} else {
if (consonant == null) {
consonant = new Node(x);
end = consonant;
} else {
consonant.next = new Node(x);
consonant = consonant.next;
}
}
head = head.next;
}
// In case when there is no vowel in the incoming LL
// then we have to return the head of the consonant LL
if (start == null)
return end;
// Connecting the vowel and consonant LL
vowel.next = end;
return start;
}
// Driver code
public static void Main(String[] args) {
Node head = null;
head = append(head, 'a');
head = append(head, 'b');
head = append(head, 'c');
head = append(head, 'e');
head = append(head, 'd');
head = append(head, 'o');
head = append(head, 'x');
head = append(head, 'i');
Console.Write("Linked list before :\n");
printlist(head);
head = arrange(head);
Console.Write("Linked list after :\n");
printlist(head);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
/* javascript program to arrange consonants and
vowels nodes in a linked list */
/* A linked list node */
class Node {
constructor(x) {
this.data = x;
this.next = null;
}
}
/* Function to add new node to the List */
function append(headRef, data) {
var new_node = new Node(data);
var last = headRef;
if (headRef == null) {
headRef = new_node;
return headRef;
}
while (last.next != null)
last = last.next;
last.next = new_node;
return headRef;
}
// utility function to print linked list
function printlist(head) {
if (head == null) {
document.write("Empty List\n");
return;
}
while (head != null) {
document.write(head.data + " ");
if (head.next != null)
document.write("-> ");
head = head.next;
}
document.write();
}
/*
* function to arrange consonants and vowels nodes
*/
function arrange(head) {
var vowel = null, consonant = null, start = null, end = null;
while (head != null) {
var x = head.data;
// Checking the current node data is vowel or
// not
if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u') {
if (vowel == null) {
vowel = new Node(x);
start = vowel;
} else {
vowel.next = new Node(x);
vowel = vowel.next;
}
} else {
if (consonant == null) {
consonant = new Node(x);
end = consonant;
} else {
consonant.next = new Node(x);
consonant = consonant.next;
}
}
head = head.next;
}
// In case when there is no vowel in the incoming LL
// then we have to return the head of the consonant LL
if (start == null)
return end;
// Connecting the vowel and consonant LL
vowel.next = end;
return start;
}
// Driver code
var head = null;
head = append(head, 'a');
head = append(head, 'b');
head = append(head, 'c');
head = append(head, 'e');
head = append(head, 'd');
head = append(head, 'o');
head = append(head, 'x');
head = append(head, 'i');
document.write("Linked list before :<br/>");
printlist(head);
head = arrange(head);
document.write("<br/>Linked list after :<br/>");
printlist(head);
// This code is contributed by Rajput-Ji
</script>
Producción
Linked list before : a -> b -> c -> e -> d -> o -> x -> i Linked list after : a -> e -> o -> i -> b -> c -> d -> x
COMPLEJIDAD DE TIEMPO:- O(n)
COMPLEJIDAD DE ESPACIO:- O(n)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA