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 * findMiddleOfLinkedList(struct node * head)
{
	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;
    while(head)
    {
        nextNode = head -> next;
        head -> next = temp;
        temp = head;
        head = nextNode;
    }
    return temp;
}

//function to get the number of nodes
int getCount(struct node * head)
{
	int count = 0;
	while(head)
	{
		count++;
		head = head -> next;
	}
	return count;
}

void printList(struct node * head)
{
	while(head != NULL)
	{
		printf("%d ",head->data);
		head = head->next;
	}
}

// defining a function to determine if a List is a Palindrome or not
int isPalindrome(struct node * head)
{
	int flag = 1;

	// get the count of the List
	int count = getCount(head);

	// variable to get the middle of the List
	struct node * middle = findMiddleOfLinkedList(head);

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

	// now "middle" point to the MID of the Linked List
	// "head" points to the start 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;
		}

		// advance both the pointers
		head = head -> next;
		middle = middle -> next;
	}

	return flag;
}

struct node * addElement(struct node *head, int number)
{
	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;
	return head;
}

int main(void)
{
	//creating a list
	struct node * listHead = (struct node*)malloc(sizeof(struct node));
	listHead->data = 1;
	listHead->next = NULL;
	listHead = addElement(listHead, 2);
	listHead = addElement(listHead, 3);
	listHead = addElement(listHead, 4);
	listHead = addElement(listHead, 4);
	listHead = addElement(listHead, 3);
	listHead = addElement(listHead, 2);
	listHead = addElement(listHead, 1);

	if(isPalindrome(listHead))
		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.