Problem Statement

Given the head of a singly linked list, return true if it is a palindrome.

Example 1:

Input: head = [1,2,2,1]
Output: true

Problem Link

Palindrome Linked List - LeetCode

Approach

1. Spilt the linked list in middle
2. Prepare two linked lists.
3. If odd ignore the middle one
4. Reverse the second linked list.
5. Compare the two lists.

Code

void check_palindrome(node *start)
{
node *p , *q ,*first_start,*second_start;
p = start;
q = start;
if(p->next == NULL)          // if there is only one character in the string
{
	printf("It is a palindrome");
	return;
}
//split the linked list
while(1)
{
	p = p->next->next;
	if(p == NULL)
	{
		second_start = q->next;
		break;
	}
	if(p->next == NULL)
	{
		second_start = q->next->next;
		break;
	}
	q = q->next;
}
q->next = NULL;
//reverse the second linked list
second_start = reverse(second_start);
first_start = start;

while(first_start!=NULL && second_start!=NULL) //compare the two strings
{
	if(first_start->data == second_start->data)
	{
		first_start = first_start->next;
		second_start = second_start->next;
	}
	else
	{
		printf("\\\\n Not a Palindrome");
		return;
	}
}
printf("It is a palindrome");

}