palindrome_list_rec.c

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

#define true 1
#define false 0

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

typedef struct Node {
  int data;
  struct Node * next;
} Node;

Node * createNode(int val){
  Node * temp = (Node *)malloc(sizeof(Node));
  if(temp){
    temp->data = val;
    temp->next = NULL;
  }
  return temp;
}
/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}
void printList(Node *head){
	while(head){
		printf("%d->", head->data);
		head = head->next;
	}
	printf("Null");
}

int isPalindromeUtil(Node **forward, Node *backward){
	//There are no nodes is lists
	if(!backward) return true;
	
	/*we are recursing moving backward pointer ahead. Backward pointer will
	start moving backward once we hit above terminal condition of recursion */
	int isPalindrome = isPalindromeUtil(forward, backward->next);
	
	if(!isPalindrome) return isPalindrome;
	/*At this point forward is n nodes ahead from start and backward n 
	nodes away from end n varies from 0 to n 
	Compare forwad and backward
	*/
	if((*forward)->data != backward->data){
		return false;
	}
	//Move ahead forward pointer, backward will move back automatically due to recursion
	*forward = (*forward)->next;
	
	return isPalindrome;
}
int isPalindromeListRecursiveMethod(Node *head){
	/* we are starting with forward pointer and backward at head.
	Notice that we passing reference to forward and just pointer for 
	backward pointer */
    return isPalindromeUtil(&head, head);
}
int main(void) {
	
	Node *head = NULL;
	push(&head, 3);
	push(&head, 4);
	push(&head, 5);
	push(&head, 6);
	push(&head, 5);
	push(&head, 4);
	push(&head, 2);
	printf("\nOriginal list :");
	printList(head);
  printf("\nIs list palindrome : %s", isPalindromeListRecursiveMethod(head) ? "true" :"false");
	return 0;
}