Given a linked list, check if it is a palindrome or not. Solution in C++

Solution to this problem can be found in 3 steps:

1. First find the middle of the linked list
2. Reverse the linked list from the middle
3. Compare both of the linked lists.

Solution in C++

#include<iostream>
#include<vector>
#include<string>
 
using namespace std;
 
struct Node
{
	int data;
	Node *next;
 
	Node(int x)
	{
		data = x;
		next = NULL;
	}
};

bool isPalindrome(Node* head) 
{
	if(!head) return true;

	Node* slow = head;
	Node* fast = slow->next;

	// get the middle element
	while(fast && fast->next && fast->next->next) 
	{
		slow = slow->next;
		fast = fast->next->next;
	}

	// assign one more pointer for new head
	Node* head2 = slow->next;
	slow->next = NULL;

	Node* prev = NULL;
	Node* cur = head2;
	Node* next = NULL;

 //reverse the linked list from the middle
	while(head2) 
	{
		next = head2->next;
		head2->next = prev;
		prev = head2;
		head2 = next;
	}

  ///check if both of the linked lists are same
	head2 = prev;
	while(head && head2) 
	{
		if(head->data != head2->data)
			return false;

		head = head->next;
		head2 = head2->next;
	}

	return true;
}




 int main()
{
	Node *head = new Node(1);
	head -> next = new Node(2);
	head -> next -> next = new Node(3);
	head -> next -> next -> next = new Node(2);
	head -> next -> next -> next  -> next = new Node(1);

 
	if (isPalindrome(head))
		cout<<"The linked list is palindrome"<<endl;
	else
		cout<<"The linked list is not palindrome"<<endl;
 
	return 0;
}

Output:

The linked list is palindrome