Comprobar si una lista de caracteres doblemente enlazada es palíndromo o no

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. 

1. Cree una lista doblemente enlazada donde cada Node contenga solo un carácter de una string.
2. Inicialice dos punteros a la izquierda al principio de la lista ya la derecha al final de la lista.
3. 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++ 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 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 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# 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

<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>

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.