Dada una lista enlazada de alfabetos y caracteres especiales. Invierta la lista enlazada dada sin afectar la posición de los caracteres especiales.
Ejemplos:
Entrada : g -> @ -> e -> # -> e -> $-> k -> s -> NULL
Salida : s -> @ -> k -> # -> e -> $-> e -> g -> NULL
Explicación : aquí podemos ver que en la salida la posición del carácter especial no cambia y también la lista vinculada es inversa.
La idea es recorrer la lista enlazada y almacenar los caracteres excluyendo los caracteres especiales en una array temporal. Nuevamente recorra la lista enlazada y copie elementos de la array a los Nodes de la lista enlazada de manera inversa.
A continuación se muestra el algoritmo paso a paso :
- Tome una array temporal, TEMP_ARR.
- Recorra la lista enlazada y haga lo siguiente
- si el elemento actual es un alfabeto, almacene ese elemento de la lista enlazada en TEMP_ARR.
- de lo contrario, aumente el puntero de Node en uno
- Nuevamente recorra la lista enlazada desde el encabezado y TEMP_ARR desde el final y haga lo siguiente:
- si el elemento actual es un alfabeto, copie el último elemento de TEMP_ARR al Node de la lista enlazada actual y reduzca el índice actual de TEMP_ARR para la siguiente iteración.
- de lo contrario, aumentar el Node en uno
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to reverse a linked list
// without affecting special characters
#include <iostream>
using namespace std;
// Link list node
struct Node {
char data;
struct Node* next;
};
// Function to reverse the linked list
// without affecting special characters
void reverse(struct Node** head_ref, int size)
{
struct Node* current = *head_ref;
char TEMP_ARR[size];
int i = 0;
// Traverse the linked list and insert
// linked list elements to TEMP_ARR
while (current != NULL) {
// if the current data is any alphabet than
// store it in to TEMP_ARR
if ((current->data >= 97 && current->data <= 122) ||
(current->data >= 65 && current->data <= 90)) {
TEMP_ARR[i++] = current->data;
current = current->next;
}
// else increase the node position
else
current = current->next;
}
current = *head_ref;
// Traverse the linked list again
while (current != NULL)
{
// if current character is an alphabet than
// replace the current element in the linked list
// with the last element of the TEMP_ARR
if ((current->data >= 97 && current->data <= 122) ||
(current->data >= 65 && current->data <= 90)) {
current->data = TEMP_ARR[--i];
current = current->next;
}
// else increase the node
else
current = current->next;
}
}
// Function to push a node
void push(struct Node** head_ref, char new_data)
{
/* allocate node */
struct Node* new_node = new Node();
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print linked list */
void printList(struct Node* head)
{
struct Node* temp = head;
while (temp != NULL) {
cout << temp->data;
temp = temp->next;
}
}
// Driver program to test above function
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
push(&head, 's');
push(&head, '$');
push(&head, 'k');
push(&head, 'e');
push(&head, 'e');
push(&head, '@');
push(&head, '#');
push(&head, 'g');
push(&head, 'r');
push(&head, 'o');
push(&head, 'f');
push(&head, 's');
push(&head, '$');
push(&head, 'k');
push(&head, 'e');
push(&head, 'e');
push(&head, 'g');
cout << "Given linked list: ";
printList(head);
reverse(&head, 13);
cout << "\nReversed Linked list: ";
printList(head);
return 0;
}
Java
// Java program to reverse a
// linked list without affecting
// special characters
class GFG
{
// Link list node
public static class Node
{
char data;
Node next;
}
// Function to reverse the linked
// list without affecting special
// characters
static void reverse(Node head_ref,
int size)
{
Node current = head_ref;
char TEMP_ARR[] = new char[size];
int i = 0;
// Traverse the linked list
// and insert linked list
// elements to TEMP_ARR
while (current != null)
{
// if the current data
// is any alphabet than
// store it in to TEMP_ARR
if ((current.data >= 97 &&
current.data <= 122) ||
(current.data >= 65 &&
current.data <= 90))
{
TEMP_ARR[i++] = current.data;
current = current.next;
}
// else increase the node position
else
current = current.next;
}
current = head_ref;
// Traverse the linked list again
while (current != null)
{
// if current character is an
// alphabet than replace the
// current element in the linked
// list with the last element
// of the TEMP_ARR
if ((current.data >= 97 &&
current.data <= 122) ||
(current.data >= 65 &&
current.data <= 90))
{
current.data = TEMP_ARR[--i];
current = current.next;
}
// else increase the node
else
current = current.next;
}
}
// Function to push a node
static Node push(Node head_ref,
char new_data)
{
/* allocate node */
Node new_node = new Node();
/* put in the data */
new_node.data = new_data;
/* link the old list
off the new node */
new_node.next = (head_ref);
/* move the head to point
to the new node */
(head_ref) = new_node;
return head_ref;
}
/* Function to print linked list */
static void printList(Node head)
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data);
temp = temp.next;
}
}
// Driver Code
public static void main(String rags[])
{
/* Start with the empty list */
Node head = null;
head = push(head, 's');
head = push(head, '$');
head = push(head, 'k');
head = push(head, 'e');
head = push(head, 'e');
head = push(head, '@');
head = push(head, '#');
head = push(head, 'g');
head = push(head, 'r');
head = push(head, 'o');
head = push(head, 'f');
head = push(head, 's');
head = push(head, '$');
head = push(head, 'k');
head = push(head, 'e');
head = push(head, 'e');
head = push(head, 'g');
System.out.print( "Given linked list: ");
printList(head);
reverse(head, 13);
System.out.print("\nReversed Linked list: ");
printList(head);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to reverse a linked list
# without affecting special characters
# Link list node
class Node:
def __init__(self, x):
self.data = x
self.next = None
# Function to reverse the linked list
# without affecting special characters
def reverse(head_ref, size):
current = head_ref
TEMP_ARR = [0 for i in range(256)]
i = 0
# Traverse the linked list and insert
# linked list elements to TEMP_ARR
while (current != None):
# If the current data is any alphabet than
# store it in to TEMP_ARR
if ((ord(current.data) >= 97 and
ord(current.data) <= 122) or
(ord(current.data) >= 65 and
ord(current.data) <= 90)):
TEMP_ARR[i]= current.data
i += 1
current = current.next
# Else increase the node position
else:
current = current.next
current = head_ref
# Traverse the linked list again
while (current != None):
# If current character is an alphabet
# than replace the current element in
# the linked list with the last element
# of the TEMP_ARR
if ((ord(current.data) >= 97 and
ord(current.data) <= 122) or
(ord(current.data) >= 65 and
ord(current.data) <= 90)):
i = i - 1
current.data = TEMP_ARR[i]
current = current.next
# Else increase the node
else:
current = current.next
return head_ref
# Function to push a node
def push(head_ref, new_data):
# Allocate node
#new_node = (struct Node*)malloc(sizeof(struct Node));
# Put in the data
new_node = Node(new_data)
# Link the old list off the new node
new_node.next = head_ref
# Move the head to point to the new node
head_ref = new_node
return head_ref
# Function to print linked list
def printList(head):
temp = head
while (temp != None):
print(temp.data, end = "")
temp = temp.next
# Driver code
if __name__ == '__main__':
# Start with the empty list
head = None
head = push(head, 's')
head = push(head, '$')
head = push(head, 'k')
head = push(head, 'e')
head = push(head, 'e')
head = push(head, '@')
head = push(head, '#')
head = push(head, 'g')
head = push(head, 'r')
head = push(head, 'o')
head = push(head, 'f')
head = push(head, 's')
head = push(head, '$')
head = push(head, 'k')
head = push(head, 'e')
head = push(head, 'e')
head = push(head, 'g')
print("Given linked list: ", end = "")
printList(head)
head = reverse(head, 13)
print("\nReversed Linked list: ", end = "")
printList(head)
# This code is contributed by mohit kumar 29
C#
// C# program to reverse a
// linked list without affecting
// special characters
using System;
class GFG
{
// Link list node
public class Node
{
public char data;
public Node next;
}
// Function to reverse the linked
// list without affecting special
// characters
static void reverse(Node head_ref,
int size)
{
Node current = head_ref;
char []TEMP_ARR = new char[size];
int i = 0;
// Traverse the linked list
// and insert linked list
// elements to TEMP_ARR
while (current != null)
{
// if the current data
// is any alphabet than
// store it in to TEMP_ARR
if ((current.data >= 97 &&
current.data <= 122) ||
(current.data >= 65 &&
current.data <= 90))
{
TEMP_ARR[i++] = current.data;
current = current.next;
}
// else increase the node position
else
current = current.next;
}
current = head_ref;
// Traverse the linked list again
while (current != null)
{
// if current character is an
// alphabet than replace the
// current element in the linked
// list with the last element
// of the TEMP_ARR
if ((current.data >= 97 &&
current.data <= 122) ||
(current.data >= 65 &&
current.data <= 90))
{
current.data = TEMP_ARR[--i];
current = current.next;
}
// else increase the node
else
current = current.next;
}
}
// Function to push a node
static Node push(Node head_ref,
char new_data)
{
/* allocate node */
Node new_node = new Node();
/* put in the data */
new_node.data = new_data;
/* link the old list
off the new node */
new_node.next = (head_ref);
/* move the head to point
to the new node */
(head_ref) = new_node;
return head_ref;
}
/* Function to print linked list */
static void printList(Node head)
{
Node temp = head;
while (temp != null)
{
Console.Write(temp.data);
temp = temp.next;
}
}
// Driver Code
public static void Main(String []rags)
{
/* Start with the empty list */
Node head = null;
head = push(head, 's');
head = push(head, '$');
head = push(head, 'k');
head = push(head, 'e');
head = push(head, 'e');
head = push(head, '@');
head = push(head, '#');
head = push(head, 'g');
head = push(head, 'r');
head = push(head, 'o');
head = push(head, 'f');
head = push(head, 's');
head = push(head, '$');
head = push(head, 'k');
head = push(head, 'e');
head = push(head, 'e');
head = push(head, 'g');
Console.Write( "Given linked list: ");
printList(head);
reverse(head, 13);
Console.Write("\nReversed Linked list: ");
printList(head);
}
}
// This code has been contributed
// by 29AjayKumar
Javascript
<script>
// JavaScript program to reverse a
// linked list without affecting
// special characters
// Link list node
class Node
{
constructor()
{
let data,next;
}
}
// Function to reverse the linked
// list without affecting special
// characters
function reverse(head_ref,size)
{
let current = head_ref;
let TEMP_ARR = new Array(size);
let i = 0;
// Traverse the linked list
// and insert linked list
// elements to TEMP_ARR
while (current != null)
{
// if the current data
// is any alphabet than
// store it in to TEMP_ARR
if ((current.data.charCodeAt(0) >= 97 &&
current.data.charCodeAt(0) <= 122) ||
(current.data.charCodeAt(0) >= 65 &&
current.data.charCodeAt(0) <= 90))
{
TEMP_ARR[i++] = current.data;
current = current.next;
}
// else increase the node position
else
current = current.next;
}
current = head_ref;
// Traverse the linked list again
while (current != null)
{
// if current character is an
// alphabet than replace the
// current element in the linked
// list with the last element
// of the TEMP_ARR
if ((current.data.charCodeAt(0) >= 97 &&
current.data.charCodeAt(0) <= 122) ||
(current.data.charCodeAt(0) >= 65 &&
current.data.charCodeAt(0) <= 90))
{
current.data = TEMP_ARR[--i];
current = current.next;
}
// else increase the node
else
current = current.next;
}
return head_ref;
}
// Function to push a node
function push(head_ref,new_data)
{
/* allocate node */
let new_node = new Node();
/* put in the data */
new_node.data = new_data;
/* link the old list
off the new node */
new_node.next = (head_ref);
/* move the head to point
to the new node */
(head_ref) = new_node;
return head_ref;
}
/* Function to print linked list */
function printList(head)
{
let temp = head;
while (temp != null)
{
document.write(temp.data);
temp = temp.next;
}
}
// Driver Code
/* Start with the empty list */
let head = null;
head = push(head, 's');
head = push(head, '$');
head = push(head, 'k');
head = push(head, 'e');
head = push(head, 'e');
head = push(head, '@');
head = push(head, '#');
head = push(head, 'g');
head = push(head, 'r');
head = push(head, 'o');
head = push(head, 'f');
head = push(head, 's');
head = push(head, '$');
head = push(head, 'k');
head = push(head, 'e');
head = push(head, 'e');
head = push(head, 'g');
document.write( "Given linked list: ");
printList(head);
head=reverse(head, 13);
document.write("<br>Reversed Linked list: ");
printList(head);
// This code is contributed by unknown2108
</script>
Producción:
Given linked list: geek$sforg#@eek$s Reversed Linked list: skee$grofs#@kee$g
Complejidad de tiempo: O(N), donde N es el número total de Nodes en la lista enlazada.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Shahnawaz_Ali y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA