## 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.

### Example

## 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.

ReverseLinkedlist(middle)

**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.

### Algorithm working example

## C++ Program

```
#include <bits/stdc++.h>
using namespace std;
struct LL{
int data;
LL *next;
};
void insertAtBeginning(struct LL**head,int dataToBeInserted)
{
struct LL* curr=new LL;
curr->data=dataToBeInserted;
curr->next=NULL;
if(*head==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
*head=curr;
}
//O(1) constant time
}
void reverseListIteratively(struct LL **head)
{
struct LL *temp=NULL,*prev=NULL,*curr=*head;
while(curr!=NULL)
{
temp=curr->next;
curr->next=prev;
prev=curr;
curr=temp;
}
*head=prev;
//O(number of nodes)
}
struct LL* middleOfList(struct LL**head)
{
struct LL*slow=*head,*fast=*head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
//O(number of nodes)
}
void display(struct LL**head)
{
struct LL*temp=*head;
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)
{
if(middle->data != head->data)
return false;
head = head->next;
middle = middle->next;
}
return true;
}
int main()
{
struct LL *head = NULL; //initial list has no elements
insertAtBeginning(&head,23);
insertAtBeginning(&head,49);
insertAtBeginning(&head,12);
insertAtBeginning(&head,15);
insertAtBeginning(&head,16); // uncomment to check and see that it is a palindrome
insertAtBeginning(&head,12);
insertAtBeginning(&head,49);
insertAtBeginning(&head,23);
cout<<"Given List is :-\n";
display(&head);
struct LL * middle = middleOfList(&head);
reverseListIteratively(&middle);
if(isPalin(head,middle))
cout<<"\nGiven list is a palindrome\n";
else
cout<<"\nGiven list is not a palindrome \n";
return 0;
}
```