• • Write a c program to check whether given link list is palindrome?  Each node of a linked list represents a number in it. From the below figure it is clear that the linked list 1->2->3->2->1 is a palindrome.

## How to check whether given link list is palindrome

There are various methods to check palindrome. The question is asked in the interview, so it is better to write less complexity based code. Lets discuss each method and its advantages.

## (1) Recursive method: Time complexity O(n)

```#include<stdio.h>
#include <stdlib.h>

#define true 1
#define false 0
// link list data structure
typedef struct link_
{
int a;
struct link *next;
} link;

link *head = NULL;
void append (int a);
int checkforpalindrome (link * head);
void freelink()
{
link* tmp;

while (head != NULL)
{
tmp = head;
head = head->next;
free(tmp);
}

}
int main ()
{
append (1);
append (2);
append (3);
append (2);
append (1);

if (checkforpalindrome (head))
printf ("link list palindrome\n");
else
printf ("link list not palindrome\n");

freelink();
return 0;
}

void append (int a)
{
// if empty
if (head == NULL)
{
head = (link *) malloc (sizeof (link));
head->a = a;
head->next = NULL;
}
else
{
link *tmp = head;
// go to last node
while (tmp->next != NULL)
tmp = tmp->next;

// append data
link *p = (link *) malloc (sizeof (link));
p->a = a;
tmp->next = p;
p->next = NULL;
}
}

int checkforpalindrome (link * pp)
{
// base terminatig condition for recursion
if (pp == NULL)
return true;

// call checkforpalindrome
/* calling on next node, make pp->next on stack */
checkforpalindrome (pp->next);

/* now pp will point to last node */
/* compare last node to first node */
int flag = false;
if (head->a == pp->a)
{
flag = true;
}
else
{
flag = false;
}
// advance the head on next node
head = head->next;

return flag;
}```