Simple C Program to check if the given linked list is palindrome

Consider the following linked list

a->b->c->c->b->a->null is palindrome .
there are two ways to find out whether the given linked list is a palindrome or not

1. Use stack . push the first half of the linked list into stack and pop elements from stack & check it with the second half .But it needs extra space.

2. Reverse the second half of the linked list .so it will become a->b->c->a->b->c->null .Compare the first half with the second half . Here u need to find the length of the linked list and reverse of linked list .Its already posted in this site. That's of the beauty of writing functions . U can reuse it whenever u want . Refer it here if u want
i)  Length of the linked list
ii) Code to reverse the linked list .

Code: (in C)

int check_palindrome(struct node* head)
{
int length=size_of_linkedlist(head),middle;
if(length < 2)
return 1;
struct node* first_half=head,second_half=head,reversed_second_half,temp;

  // find the middle element and move the second_half pointer to second half
if(length%2==0)
middle=length/2+1;
else
middle=length/2+2;
while(--middle!=0)
second_half=second_half->link;

//reverse the second half of the linked list
temp=reversed_second_half=reverse(second_half);

//compare first half and second half
while(temp!=null)
{
if(temp->data != first_half->data)
{
second_half=reverse(reversed_second_half);
return 0;
}
temp=temp->link;
}

//reverse again the second half so that original list wont be changed .
second_half=reverse(reversed_second_half);
return 1;
}

Please let me know if there is any bug in the above code and your suggestions are always welcome .

Simple recursive code to find the size of linked list and binary tree

Finding the size of the linked list and binary tree is very easy using recursion . U just need to traverse every node and increment count.

Code: (in  C)

Size of Linked list:

int size_of_linkedlist(struct node* node)
{
if(node==null)
return 0;
return 1+size_of_linkedlist(node->link);
}

Size of Binary tree:

int size_of_binarytree(struct node* node)
{
if(node==null)
return 0;
return 1+size_of_binarytree(node->left)+size_of_binarytree(node->right);
}

Please let me know if u find any bug in above code and your suggestions are always welcome .

A Simple C Code for Binary Tree Traversal

Three traversal methods
     i)   preorder traversal
     ii)  inorder traversal
     iii) postorder traversal

This post may seem very simple . But to solve the problems related to binary trees you should have clear understanding of these traversals . For an example ,creating mirror image of the tree depends on postorder traversal .
Consider the following tree

 Preorder  :  A B C D E F G
 Inorder   :   C B D A F E G
 Postorder : C D B F G E A

 Code :(in C)

 Preorder Traversal :

 void preorder_traversal(struct node * node)
 {
if(node!=null)
{
printf("%d ",node->data);
preorder_traversal(node->left);
preorder_traversal(node->right);
}
 }

 Inorder Traversal :

 void inorder_traversal(struct node * node)
 {
if(node!=null)
{
inorder_traversal(node->left);
printf("%d ",node->data);
inorder_traversal(node->right);
}
 }

 Postorder Traversal :

 void postorder_traversal(struct node * node)
 {
if(node!=null)
{
postorder_traversal(node->left);
postorder_traversal(node->right);
printf("%d ",node->data);
}
 }

Please let me know if there is any bug in the above code and your suggestions are always welcome .