Dada una lista vinculada que maneja datos de strings, verifique si los datos son palíndromos o no. Ejemplos:
Input: a -> bc -> d -> dcb -> a -> NULL Output: True String "abcddcba" is palindrome. Input: a -> bc -> d -> ba -> NULL Output: False String "abcdba" is not palindrome.
La idea es muy simple. Construya una string a partir de una lista enlazada dada y verifique si la string construida es palíndromo o no.
C++
// Program to check if a given linked list
// of strings form a palindrome
#include <bits/stdc++.h>
using namespace std;
// Link list node
struct Node
{
string data;
Node* next;
};
// A utility function to check if str
// is palindrome or not
bool isPalindromeUtil(string str)
{
int length = str.length();
// Match characters from beginning
// and end.
for (int i = 0; i < length / 2; i++)
if (str[i] != str[length - i - 1])
return false;
return true;
}
// Returns true if string formed by linked
// list is palindrome
bool isPalindrome(Node *node)
{
// Append all nodes to form a string
string str = "";
while (node != NULL)
{
str.append(node->data);
node = node->next;
}
// Check if the formed string is
// palindrome
return isPalindromeUtil(str);
}
// A utility function to print a given
// linked list
void printList(Node *node)
{
while (node != NULL)
{
cout << node->data << " -> ";
node = node->next;
}
printf("NULL");
}
/* Function to create a new node with
given data */
Node *newNode(const char *str)
{
Node *new_node = new Node;
new_node->data = str;
new_node->next = NULL;
return new_node;
}
// Driver code
int main()
{
Node *head = newNode("a");
head->next = newNode("bc");
head->next->next = newNode("d");
head->next->next->next =
newNode("dcb");
head->next->next->next->next =
newNode("a");
isPalindrome(head)? printf("true"):
printf("false");
return 0;
}
Producción:
true
Complejidad de tiempo: O(n), donde n es el número de Nodes en la lista enlazada dada.
Espacio Auxiliar: O(m), donde m es la longitud de la string formada por la lista enlazada.
Consulte el artículo completo sobre Comprobar si una lista enlazada de strings forma un palíndromo para obtener más detalles.
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