# Check if the linked list is palindrome

0
515

## Given a singly linked list, find whether itâ€™s a palindrome are not

Palindrome : an integer or a string that reads the same backwards as forwards.

## Algorithm

Time Complexity : O(n)

Step 1 : Get the middle of the given linked list.

a)Â Â Â  Create two dummy linked lists (fast and slow).
b)Â Â Â  Slow and fast are copies of given linked lists.
c)Â Â Â  Traverse through the lists such that until fast->next = null move two positions in fast and one position in slow.
d)Â Â Â  return slow.
Returns pointer of the mid node.

Step 2 : Reverse the left part of the linked list using reverse linked list function.

Step 3 : compare the left and right parts of the linked lists by creating a function ispalindrome which takes the full linked list and reversed left part.

a)Â Â Â  If the left part is identical to the right part, print is palindrome
b)Â Â Â  Else, Not a palindrome.

## C++ Program

``````#include <bits/stdc++.h>
using namespace std;

struct LL{
int data;
LL *next;
};

{
struct LL* curr=new LL;

curr->data=dataToBeInserted;
curr->next=NULL;

*head=curr; //if this is first node make this as head of list

else
{
curr->next=*head; //else make the current (new) node's next point to head and make this new node a the head
}

//O(1) constant time
}

{
while(curr!=NULL)
{
temp=curr->next;
curr->next=prev;
prev=curr;
curr=temp;
}
//O(number of nodes)
}

{

while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
return  slow;
//O(number of nodes)
}

{
while(temp!=NULL)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;

temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}

bool isPalin(struct LL *head, struct LL *middle)
{

while(middle != NULL)
{
return false;
middle = middle->next;
}

return true;
}

int main()
{

struct LL *head = NULL; //initial list has no elements
insertAtBeginning(&head,16); // uncomment to check and see that it is a palindrome

cout<<"Given List is :-\n";

struct LL * middle = middleOfList(&head);
reverseListIteratively(&middle);