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

Introduction

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.

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

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

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

  • 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

Code Implementation


#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: O(n), as list traversal is needed.

So, in this article, we have tried to explain the most efficient approach to check if a doubly-linked list of characters is palindrome or not. 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.

Previous post Sort a linked list that is sorted alternating ascending and descending orders
Next post LinkedList addFirst() Method in Java

Leave a Reply

Your email address will not be published. Required fields are marked *