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.

Check whether given link list is palindromeHow 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;
}

(2) Reverse the second half method:

 



Related Contents to follow