Linked List: Check if a doubly linked list of characters is palindrome or not

Solution:

Step 1: Take two pointers, “right_pointer” will point to the end of the list, “left_pointer” will point to the beginning of the list.

Step 2: Check the data in the list, if they are same increment the left_pointer and decrement the right_pointer. In any case if the values are different, then return false.

Solution in C++

#include<iostream>
#include<vector>
#include<string>

using namespace std;


struct Node
{
	string data;
	Node *prev;
	Node *next;
};

//global head pointer
Node *head;

void insert(string data)
{
	Node *temp=head;

	if (head!=NULL)
	{
		while(temp->next!=NULL)
		{
			temp = temp->next;
		}
		Node *new_node= new Node;
		temp->next=new_node;
		new_node->prev=temp;
		new_node->data=data;
		new_node->next=NULL;
	}
	else
	{
		// if this is the first node
		Node *new_node= new Node;
		new_node->data=data;
		new_node->prev=NULL;
		new_node->next=NULL;
		head = new_node;
	}
}

void display_list()
{
	Node *temp = head;
	while(temp!=NULL)
	{
		cout<<temp->data<<" <-> ";
		temp = temp->next;
	}
	cout<<endl;
}

bool check_palindrome()
{
	
	Node *right_pointer = head;
	Node *left_pointer = head;

	//get to the end of the list
	while (right_pointer->next != NULL)
		right_pointer = right_pointer->next;

	while (left_pointer != right_pointer)
	{
		if (left_pointer->data != right_pointer->data)
			return false;

		left_pointer = left_pointer->next;
		right_pointer = right_pointer->prev;
	}
	return true;

}


int main()
{
	insert("h");
	insert("a");
	insert("j");
	insert("a");
	insert("h");


	cout<<"The list is "<<endl;
	display_list();

	if(check_palindrome())
		cout<<"The list is palindrome"<<endl;
	else
		cout<<"The list not is palindrome"<<endl;


	return 0;
}