Check if a doubly-linked list of characters is palindrome or not

Introduction

In this article, we will discuss how to check if characters are palindrome in doubly linked list. The characters read the same backward as forward. Some examples of palindromic words are redivider, deified, civic, radar, level, rotor, kayak, reviver, racecar, madam, and refer. The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.Let’s discuss how to check if characters are palindrome in doubly linked list.

Problem Statement

In this problem, we are given a doubly-linked list of characters. We have to check if the given list is palindrome or not.

Problem Statement Understanding How To Check Palindrome In Doubly Linked List

This question is not a very complex one. We have to check if the given doubly linked list of characters is palindrome or not. A list is said to be palindrome, if it reads the same backwards as forwards.

Input:

Output: Palindrome

Explanation: The given list of characters is palindrome.

We can use the two-pointers method to solve this. Can you guess why we are using the two-pointers method? Yes, with the help of this method, we can solve this problem by only doing a single traversal of the given list. This approach is going to take O(n) time. Let us have a glance at the approach.

Approach For Checking Palindrome In Doubly Linked List

As mentioned earlier, we are going to use the two pointers technique here. We will create two pointers, left and right. The left pointer will point at the head of the list, while the right pointer will point at the end of the list. To make the right pointer point to the end of the list, we will make it initially point to the head. Then, we will increment it till we reach the end of the list.

Now, we will compare the left and right pointers. If equal, then we will increment the left pointer and decrement the right pointer. If at any point, the value at the left pointer is not equal to the value at the right pointer, then we will return false as the list is not palindrome.

Algorithm To Check Palindrome In Doubly Linked List

• Initialize two pointers, left and right. Left will point at the head of the list and right will point at the tail of the list.
• To make the right pointer point to the tail of the list, first, make it point to the head. Then, traverse till the end and keep increasing the right pointer. In the end, it will point at the tail.
• Compare the values at the left node and the right node. If they are equal, then increment the left pointer and decrement the right pointer till the middle of the given list.
• If, at any point, the value at the left node is not equal to the value at the right node, return false.
• In the end, return true.

Dry Run To Check Palindrome In Doubly Linked List

Code Implementation To Check If characters is Palindrome in Doubly Linked List

#include
using namespace std;
 
struct Node
{
    char data;
    struct Node *next;
    struct Node *prev;
};
 
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;
}
bool isPalindrome(struct Node *left)
{
    if (left == NULL)
       return true;
 
    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;
}
int main()
{
    struct Node* head = NULL;
    push(&head, 'c');
    push(&head, 'i');
    push(&head, 'v');
    push(&head, 'i');
    push(&head, 'c');
 
    if (isPalindrome(head))
        printf("Palindrome");
    else
        printf("Not Palindrome");
 
    return 0;
}

public class PrepBytes
{

// Structure of node
static class Node
{
    char data;
    Node next;
    Node prev;
};

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

static boolean isPalindrome(Node left)
{
    if (left == null)
    return true;

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

public static void main(String[] args)
{
    Node head = null;
    head = push(head, 'c');
    head = push(head, 'i');
    head = push(head, 'v');
    head = push(head, 'i');
    head = push(head, 'c');

    if (isPalindrome(head))
        System.out.printf("It is Palindrome");
    else
        System.out.printf("Not Palindrome");
}
}

Output
Palindrome

Time Complexity To Check Palindrome In Doubly Linked List: O(n), as list traversal is needed.

This article will help you to understand the most efficient approach to check Palindrome in doubly linked list.. This is an important problem when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

FAQ Related To Palindrome In Doubly Linked List

1. What is a double-ended linked list?

Unlike a doubly linked list which has two pointers, one pointing to the next and the other pointing to the previous node, a doubly ended linked list each node has just one pointer which points to the next .” node The difference is that instead of just one “head” node, it contains two pointers of this kind (“first” and “last”), so someone can insert elements to list from both ends of it.

2. What is the difference between single and doubly linked lists?

A singly linked list has a pointer pointing to the next node in the sequence. There is no concept of a previous pointer, and a node does not know about the previous node. While in a doubly-linked list, each node has two pointers pointing to the previous and the current node, respectively.

3. Is an empty linked list a palindrome?

If the linked list has one node or if it is empty then the linked list is palindrome.

4. What is a palindrome?

A palindrome is a sequence of characters that reads the same in both forward and reverse directions.