Home Linked List How will you check if a Linked List is palindrome or not?

# How will you check if a Linked List is palindrome or not?

Question: Write a program to check if the given Linked List is a palindrome or not?

Input:
1.> 4, 8, 15, 16, 23, 42
2.> 4, 8, 15, 16, 15, 8, 4

Output:
1.> IS NOT A PALINDROME
2.> IS A PALINDROME

#### What is a Palindrome?

According to Wikipedia, A palindrome is a word, phrase, number, or other sequence of symbols or elements, whose meaning may be interpreted the same way in either forward or reverse direction.

Thus, numbers like 121, 1331, 98711789 are palindromes.

Similarly, Linked Lists can be palindromes when they remain the same when read from the forward direction or the backward direction.

To check if a Linked List is a palindrome, we can perform the following operations on the Linked List.

• Get the middle of the Linked List
• Separate the two lists.
• Reverse the second half of the Linked List.
• Compare the first and the second half.
• If both the halves are same, then the list is a palindrome.

We have discussed, how to get the middle of a Linked List in this post.

Once we get the middle of the Linked List we separate the lists. If the list is ODD, we ignore the center node, as it will node play a part in being a palindrome, 121, 14541, 198303891 are some examples and here 2, 5, 0 do not play any part in being a palindrome.

In case of EVEN list, we get the n/2th node, and no change is needed. If list is 1, 2, 3, 3, 2, 1 we get the underlined 3.

Once we get the middle node, we can reverse the List using the method in this post.

Now we compare the Lists, till (count/2) iterations, where count = number of nodes. If at any point of time, the data is not equal, that means the List is NOT PALINDROME, else we can say that the list IS A PALINDROME.

#include<stdio.h>

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

{
struct node * slowPtr = head;
struct node * fastPtr = head;

while(fastPtr ->next != NULL)
{
slowPtr = slowPtr -> next;
fastPtr = fastPtr -> next;
if(fastPtr == NULL)
break;

fastPtr = fastPtr -> next;
if(fastPtr == NULL)
break;
}
return slowPtr;
}

struct node * reverseList(struct node * head)
{
struct node * temp = NULL;
struct node * nextNode = NULL;
{
}
return temp;
}

//function to get the number of nodes
{
int count = 0;
{
count++;
}
return count;
}

{
{
}
}

// defining a function to determine if a List is a Palindrome or not
{
int flag = 1;

// get the count of the List

// variable to get the middle of the List

// reverse the list from the middle
middle = reverseList(middle);

// now "middle" point to the MID of the Linked List

// a variable to count the number of iterations
int step = 0;

printf("count = %d\n",count);

// if ODD example = 1335331, count = 7, mid = 5, we need to go till (7/2 = 3)
// if EVEN example = 123321, count = 6, mid - 3, we need to go till (6/3 = 3)
while(step < (count/2))
{
step++;

if(head -> data != middle -> data)
{
// if there is a mismatch at any point of time, set the flag to FALSE
flag = 0;
}

middle = middle -> next;
}

return flag;
}

{
struct node * temp = (struct node*)malloc(sizeof(struct node));
temp -> data = number;
temp -> next = NULL;
struct node * temp2 = head;
while(temp2 -> next != NULL)
temp2 = temp2 -> next;
temp2 -> next = temp;
}

int main(void)
{
//creating a list
struct node * listHead = (struct node*)malloc(sizeof(struct node));

printf("IS A PALINDROME");
else
printf("IS NOT A PALINDROME");

return 0;
}


NOTE: This method changes the original Linked List, in order to retain the original list, either make a copy of the original list and then perform the operation, or reverse the middle list once again and rejoin it to the original list.

#### You may also like June 3, 2016 - 09:39

I have a better solution..
Get length of the linked list – n.
Traverse the linked list and put all first half n/2 elements in stack.
While traveling next half n/2 elements, compare the element in linked with popped element from stack.
If match occurred then move forward else the print that list is not a palindrom. June 3, 2016 - 10:50

Hi Mukesh,

Your solution is also correct. But it requires O(n/2) extra space to create a stack.
Feel free to post the solution here.