Dada una lista de caracteres doblemente enlazados, escribe una función que devuelva verdadero si la lista doblemente enlazada dada es un palíndromo, de lo contrario, falso.
- Cree una lista doblemente enlazada donde cada Node contenga solo un carácter de una string.
- Inicialice dos punteros a la izquierda al principio de la lista ya la derecha al final de la lista.
- Compruebe si los datos del Node izquierdo son iguales a los del Node derecho. Si es igual, aumente a la izquierda y disminuya a la derecha hasta la mitad de la lista. Si, en cualquier etapa, no es igual, devuelve falso.
Implementación:
C++
// C++ program to check if doubly // linked list is palindrome or not #include<bits/stdc++.h> using namespace std; // Structure of node struct Node { char data; struct Node *next; struct Node *prev; }; /* Given a reference (pointer to pointer) to the head of a list and an int, inserts a new node on the front of the list. */ void push(struct Node** head_ref, char new_data) { struct Node* new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); new_node->prev = NULL; if ((*head_ref) != NULL) (*head_ref)->prev = new_node ; (*head_ref) = new_node; } // Function to check if list is palindrome or not bool isPalindrome(struct Node *left) { if (left == NULL) return true; // Find rightmost node struct Node *right = left; while (right->next != NULL) right = right->next; while (left != right) { if (left->data != right->data) return false; left = left->next; right = right->prev; } return true; } // Driver program int main() { struct Node* head = NULL; push(&head, 'l'); push(&head, 'e'); push(&head, 'v'); push(&head, 'e'); push(&head, 'l'); if (isPalindrome(head)) printf("It is Palindrome"); else printf("Not Palindrome"); return 0; }
Java
// Java program to check if doubly // linked list is palindrome or not class GFG { // Structure of node static class Node { char data; Node next; Node prev; }; /* Given a reference (pointer to pointer) to the head of a list and an int, inserts a new node on the front of the list. */ static Node push(Node head_ref, char new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; new_node.prev = null; if (head_ref != null) head_ref.prev = new_node ; head_ref = new_node; return head_ref; } // Function to check if list is palindrome or not static boolean isPalindrome(Node left) { if (left == null) return true; // Find rightmost node Node right = left; while (right.next != null) right = right.next; while (left != right) { if (left.data != right.data) return false; left = left.next; right = right.prev; } return true; } // Driver program public static void main(String[] args) { Node head = null; head = push(head, 'l'); head = push(head, 'e'); head = push(head, 'v'); head = push(head, 'e'); head = push(head, 'l'); if (isPalindrome(head)) System.out.printf("It is Palindrome"); else System.out.printf("Not Palindrome"); } } // This code is contributed by Rajput-Ji
Python3
# Python3 program to check if doubly # linked list is a palindrome or not class Node: def __init__(self, data, next, prev): self.data = data self.next = next self.prev = prev # Given a reference (pointer to pointer) to # the head of a list and an int, inserts # a new node on the front of the list. def push(head_ref, new_data): new_node = Node(new_data, head_ref, None) if head_ref != None: head_ref.prev = new_node head_ref = new_node return head_ref # Function to check if list is palindrome or not def isPalindrome(left): if left == None: return True # Find rightmost node right = left while right.next != None: right = right.next while left != right: if left.data != right.data: return False left = left.next right = right.prev return True # Driver program if __name__ == "__main__": head = None head = push(head, 'l') head = push(head, 'e') head = push(head, 'v') head = push(head, 'e') head = push(head, 'l') if isPalindrome(head): print("It is Palindrome") else: print("Not Palindrome") # This code is contributed by Rituraj Jain
C#
// C# program to check if doubly // linked list is palindrome or not using System; class GFG { // Structure of node public class Node { public char data; public Node next; public Node prev; }; /* Given a reference (pointer to pointer) to the head of a list and an int, inserts a new node on the front of the list. */ static Node push(Node head_ref, char new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; new_node.prev = null; if (head_ref != null) head_ref.prev = new_node ; head_ref = new_node; return head_ref; } // Function to check if list is palindrome or not static bool isPalindrome(Node left) { if (left == null) return true; // Find rightmost node Node right = left; while (right.next != null) right = right.next; while (left != right) { if (left.data != right.data) return false; left = left.next; right = right.prev; } return true; } // Driver program public static void Main(String[] args) { Node head = null; head = push(head, 'l'); head = push(head, 'e'); head = push(head, 'v'); head = push(head, 'e'); head = push(head, 'l'); if (isPalindrome(head)) Console.Write("It is Palindrome"); else Console.Write("Not Palindrome"); } } // This code is contributed by Rajput-Ji
Javascript
<script> // javascript program to check if doubly // linked list is palindrome or not // Structure of node class Node { constructor() { this.data = 0; this.prev = null; this.next = null; } } /* * Given a reference (pointer to pointer) to the head of a list and an int, * inserts a new node on the front of the list. */ function push(head_ref, new_data) { var new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; new_node.prev = null; if (head_ref != null) head_ref.prev = new_node; head_ref = new_node; return head_ref; } // Function to check if list is palindrome or not function isPalindrome(left) { if (left == null) return true; // Find rightmost node var right = left; while (right.next != null) right = right.next; while (left != right) { if (left.data != right.data) return false; left = left.next; right = right.prev; } return true; } // Driver program var head = null; head = push(head, 'l'); head = push(head, 'e'); head = push(head, 'v'); head = push(head, 'e'); head = push(head, 'l'); if (isPalindrome(head)) document.write("It is Palindrome"); else document.write("Not Palindrome"); // This code contributed by umadevi9616 </script>
Producción
It is Palindrome
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Publicación relacionada:
- Función para verificar si una lista enlazada individualmente es un palíndromo
- Comprobar si una lista enlazada de strings forma un palíndromo
Este artículo es una contribución de Akash Gupta . 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.
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