CareerCup

1) Find the middle of the linked list using two pointers.
2) Reverse the linked list from the middle(second half).
3) Now two pointers, 1st one from start of list, 2nd one from middle of list.
Compare the list elements by moving pointers each time by one.
Check for palindrome property.

1.find middle node(fast runner/slow runner method)
2.construct a stack of size n/2.
3.push elements till middle point is reached.
4.at n+1th element start popping and compare with list.
(handle suituation for even and odd number of elements)

Use two pointer strategy - advance one pointer twice as fast as the other pointer. Say you advance pointer 'i' at half the speed of pointer 'j'

While pointer 'j' not at end of linked list:
1. Push everything encountered by pointer 'i' on to a stack.
2. Then advance pointer 'i' to the end, traversing each element once.
3. For each element encountered, check that it matches with element popped from stack.

The below code in C# handles both lists of even and odd sizes:

public bool IsPalindrome()
        {
            Node i=head, j=head;
            int count=1;
            bool moveBoth=false;
            Stack<Node> pal=new Stack<Node>();
            
            if(head==null) return false;
            pal.Push(i);

            while(j.next!=null)
            {
                if(moveBoth)
                {
                    i=i.next;
                    j=j.next;
                    moveBoth=false; 
                    pal.Push(i);
                }
                else
                {
                    j=j.next;
                    moveBoth=true;
                }
                count++;
            }

            if (count % 2 ==0 && i != null)
            {
                pal.Push(i.next);
            }
            while(i!=null)
            {
                if(pal.Count<1) return false;
                if(i.data.CompareTo(pal.Pop().data)!=0)
                    return false;
                i = i.next;
            }

            return true;
        }

Method-1: Use Recursion

You need to compare the first and last node in the first loop and then compress the list


bool isPalindrome(Node* head)
{
return isPalindromeRec(&head, head);
}

bool isPalindromeRec(Node **l, Node *r)
{
if (!r) // terminating condition
return true;

// If the sublist is not palindrome then don't need to check further
if (! isPalindromeRec(l, r->link) )
return false;

bool flag = (r->data == (*l)->data);

*l = (*l)->link; // Move l forward

return flag;
}


Method-2: Use reverse method

Move to the middle of the list.
Reverse the second half
compare the first and reversed second half one node at a time, if the are same return true else false.
Reverse the 2nd half again to get the original list.


Time Complexity: O(n)
Extra Space used: O(1)

This can be optimized using a doubly linked list.

1. Traverse from head and tail at the same time from node to node and check if value is the same. (head ++ and tail --)
2. continue as long as head == tail or head > tail pointer.
3. If there was no change observed in the values as head and tail in each jump then its a palindrome, else its not.

reverse the linked list and compare with the original..O(n)

Find the length of the list, and call the recursive function below.

Node * isPali(Node * head, int length){
    if(length == 1){
        return head->next;
    }
    if(length == 2){
        if(head-next->value == head->value){
            return head->next->next;
        }else{
            return null;
        }
    }
    Node *p = isPali(head->next, length-2);
    if(p == null){
        return null;
    }
    if(p->value == head->value){
        return p->next;
    }else{
        return null;
    }
}

The below code uses two pointer strategy and checks for Palindrome Lists. It is also using C++ template mechanism to make it more general.

bool checkPalindrom()
		{
			if(!head)
				return false;
			if(head->next==NULL)
				return true;
			
			Node<T> *p = head->next;
			Node<T> *q = head;
			stack<T> st;
			st.push(q->data);
			bool turn = false;
			int size = 1;
			while(p)
			{
				if(turn)
				{
					q = q->next;	
					st.push(q->data);
					turn = false;
				}
				else
				{
					turn = true;
				}
				p = p->next;
				size++;
			}
			q = q->next;
			if(size%2 != 0)
			{
				st.pop();
			}
			while(q)
			{
				if(st.top()==q->data)
				{
					q = q->next;
					st.pop();
				}
				else
				{
					return false;
				}
			} 
			return true;
		}

Use stack (recursive function or explicitly)

/*
METHOD 1 (By reversing the list)

1. Get the middle of the linked list.
2. Reverse the second half of the linked list.
3. Compare the first half and second half.
4. Construct the original linked list by reversing the
second half again and attaching it back to the first half
*/


/* Program to check if a linked list is palindrome */
#include<stdio.h>
#include<stdlib.h>
#define bool int

/* Link list node */
struct node
{
char data;
struct node* next;
};

void reverse(struct node**);
bool compareLists(struct node*, struct node *);

/* Function to check if given linked list is
palindrome or not */
bool isPalindrome(struct node *head)
{
struct node *slow_ptr = head;
struct node *fast_ptr = head;
struct node *second_half;
struct node *prev_of_slow_ptr = head;
char res;

if(head!=NULL)
{
/* Get the middle of the list. Move slow_ptr by 1
and fast_ptrr by 2, slow_ptr will have the |_n/2_|th
node */
while((fast_ptr->next)!=NULL &&
(fast_ptr->next->next)!=NULL)
{
fast_ptr = fast_ptr->next->next;

/*We need previous of the slow_ptr for
linked lists with odd elements */
prev_of_slow_ptr = slow_ptr;
slow_ptr = slow_ptr->next;
}

/* Case where we have even no of elements */
if(fast_ptr->next != NULL)
{
second_half = slow_ptr->next;
reverse(&second_half);
slow_ptr->next = NULL;
res = compareLists(head, second_half);

/*construct the original list back*/
reverse(&second_half);
slow_ptr->next = second_half;
}

/* Case where we have odd no. of elements. Neither first
nor second list should have the middle element */
else
{
second_half = slow_ptr->next;
prev_of_slow_ptr->next = NULL;
reverse(&second_half);
res = compareLists(head, second_half);

/*construct the original list back*/
reverse(&second_half);
prev_of_slow_ptr->next = slow_ptr;
slow_ptr->next = second_half;
}

return res;
}
}

/* Function to reverse the linked list Note that this
function may change the head */
void reverse(struct node** head_ref)
{
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}

/* Function to check if two input lists have same data*/
int compareLists(struct node* head1, struct node *head2)
{
struct node* temp1 = head1;
struct node* temp2 = head2;

while(temp1 && temp2)
{
if(temp1->data == temp2->data)
{
temp1 = temp1->next;
temp2 = temp2->next;
}
else return 0;
}

/* Both are empty reurn 1*/
if(temp1 == NULL && temp2 == NULL)
return 1;

/* Will reach here when one is NULL
and other is not */
return 0;
}

/* Push a node to linked list. Note that this function
changes the head */
void push(struct node** head_ref, char new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* move the head to pochar to the new node */
(*head_ref) = new_node;
}

/* Drier program to test above function*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;

push(&head, 'p');
push(&head, 'e');
push(&head, 'e');
push(&head, 'p');

/* p->e->e->p */
if(isPalindrome(head) == 1)
printf("Linked list is Palindrome");
else
printf("Linked list is not Palindrome");


return 0;
}
//Time Complexity O(n)
//Space Complexity: O(1)

use two pointers and a stack/array. One fast pointer moving two nodes a time and one slow pointer moving one node a time. Moving the two pointers at the same time. Before the faster pointer reaches the end, push the node pointed by the slow pointer to the stack. After the faster pointer reaches the end, pop the stack and compare it with the node pointed by the slow pointer. Only one time link list traversal is needed.

while(1)
{

p=head;
q=head;


while(q!=NULL && q->next!=NULL )
{
r=q;
q=q->next;
}

if(p==q || p== NULL || q==NULL)
{
printf("palindrome\n");
break;


}


if(p->value != q->value)
{

printf("Not a palindrome\n");
break;
}


r->next=NULL;
head=p->next;

}

thanks Anonymous, liked the approach.. :)

#include <stdio.h>

struct lnode {
    void *data;
    struct lnode *next;  
};

struct lnode *newNode(void *data) {
    struct lnode *node = (struct lnode *) malloc(sizeof(struct lnode));
    node->data = (char *) malloc(sizeof(strlen((char *)data)+1));
    node->next = NULL;
    strcpy((char *)node->data, (char *)data);
    return node;
}

typedef struct {
    struct lnode *top;
} Stack;

Stack *newStack() {
    Stack *s = (Stack *) malloc(sizeof(Stack));
    s->top = NULL;
    return s;
}

void *pop(Stack *s) {
    struct lnode *node;
    void *data;
    
    if(s->top==NULL)
        return NULL;
    
    node = s->top;
    s->top = node->next;
    data = node->data;
    free(node);
    return data;
}

void push(Stack *s, void *data) {
    struct lnode *node = newNode(data);
    node->next = s->top;
    s->top = node;
}

int isPalindrome(struct lnode *ll) {
    struct lnode *l2, *current;
    Stack *s = newStack();
    
    current = ll;
    while(current) {
        push(s, current);
        current = current->next;
    }
    
    current = l2 = pop(s);
    while(current) {
        current->next = pop(s);
        current = current->next;
    }
    
    while(ll!=NULL && l2!=NULL && strcmp((const char *)ll->data, (const char *)l2->data)==0) {
        ll = ll->next;
        l2 = l2->next;
    }
    return ll==NULL && l2==NULL;
}

int main() {
    struct lnode *current, *ll = NULL;
    char *words[] = {"M", "A", "L", "A", "Y", "A", "L", "A", "M"};
    int i;
    
    ll = current = newNode(words[0]);
    for(i=1; i<9; i++) {
        current->next = newNode(words[i]);
        current = current->next;
    }
    
    printf("String %s Palindrome\n", (isPalindrome(ll)) ? "Is" : "Is not");
    
    return 0;
}

@2 pointers' anonymous .. gud approach !

def test_symmetric (head):
     helper(head, head)

def helper(curr, node):
     if not curr: return node
     if curr == helper(curr.next, node)
     return node.next

ptr1=head;
ptr2=head;
mark=0;
while(ptr1!=NULL&&ptr2!=NULL)
{
push(ptr1->data);//push to stack
ptr1=ptr1->next;//move the pointer to one step
ptr2=ptr2->next;//move ptr2 to 2 steps
if(ptr2!=NULL)
ptr2=ptr2->next
else mark=1;//if length of linked list is odd
}
if(mark==1)//means odd length
pop();
ptr1=ptr1->next
while(!stack_empty()&&ptr1!=NULL)
{
compare(top_stack(),ptr1->data);
if(both r same)
pop();
else return GIVEN LL is NOT PALINDROME
}
if(stackis_empty())GIVEN LL is PALINDROME
else GIVEN LL is NOT PALINDROME

Can't you just read the value of each linked list node into a string as you traverse? Then make a new string equal to the reverse of the original string (this is a string function) and compare. If a character is not the same, return false. This runs in O(n) + O(n) = O(n) time.

we can do this by recursive call. fast pointer will be moving till the end of the list recursively and wen it reaches end thats when we start comparing the fast->data with the slow->data(where slow is in the beginning). we move slow pointer before recursive call is returned.

use 2 pointers fast and slow. when traversing slow should reverse the pointers. when fast reaches end slow reaches middle of list and all nodes before slow are reversed. now just compare reverse list with slow pointer

public class LinkPalin {

	class MyBool {
		public boolean val;

		public MyBool() {
		}
	}

	class Node {
		public char ch;
		public Node next;

		public Node(char ch) {
			this.ch = ch;
		}

		@Override
		public String toString() {
			return String.valueOf(ch);
		}
	}

	Node head = null;
	int n = 0;

	public void add(char ch) {
		Node newHead = new Node(ch);
		newHead.next = head;
		head = newHead;
		n++;
	}

	public boolean isPalin() {
		MyBool b = new MyBool();
		b.val = true;
		palin(head, b, n / 2);
		return b.val;
	}

	public Node palin(Node l, MyBool b, int depth) {
		Node r = l.next;
		if (depth > 1)
			r = palin(r, b, depth - 1);
		else if (depth == 1 && n % 2 == 1)
			r = r.next;

		b.val &= l.ch == r.ch;
		return r.next;
	}

	public void print() {
		System.out.print(n);
		System.out.print(": ");

		Node cur = head;
		while (cur != null) {
			System.out.print(cur.ch);
			System.out.print(' ');
			cur = cur.next;
		}
		System.out.println();
	}

	public void test(MyBool b) {
		b.val = false;
	}

	public static void main(String[] args) {
		LinkPalin p = new LinkPalin();
		p.add('a');
		p.add('b');
		p.add('c');
		p.add('d');
		p.add('c');
		p.add('b');
		p.add('a');

		p.print();
		System.out.print(p.isPalin());
	}
}

I have used Recursion to solve this prob:
here back pointer will start from last node and temp will start fetching nodes from start.

Please go through the code, You can also exe it... its working...!

#include<stdio.h>
#include<conio.h>
#include<malloc.h>

struct nodetype
{
int info;
struct nodetype *next;
};
typedef struct nodetype *node;

node createNode()
{
node n;
n=(node)malloc(sizeof(struct nodetype));
return n;
}



void addNode(struct nodetype **head,int in)
{
printf("1");
struct nodetype *temp,*add;
printf("2");


if(*head==NULL)
{
printf("3");
add=createNode();
printf("4");
add->info=in;
printf("5");
add->next=NULL;
printf("6");
*head=add;
printf("7");

}

else
{
temp=*head;
while(temp->next!=NULL)
{
temp=temp->next;
}
add=createNode();
add->info=in;
add->next=NULL;
temp->next=add;

}
}

void showList(struct nodetype **head)
{
node temp;
temp=*head;
if(*head==NULL)
{
printf("List is empty\n");
}
else
{

while(temp!=NULL)

{

printf("\nElement : %d",temp->info);
temp=temp->next;
}
}
}

node checkPalindrome(struct nodetype **head,struct nodetype *back)
{
node temp;
if(back->next!=NULL)
{
back=back->next;
temp=checkPalindrome(head,back);
}
if(back->next==NULL)
{
temp=*head;
}
if(back->info!=temp->info)
{

printf("\n not \n");
return temp;
}
temp=temp->next;
return temp;
}


int main()
{
int ch,item;

struct nodetype *list=NULL;

do
{
printf("\nPlease choose operation: \n");
printf("1:ADD an item \n");
printf("2:show the List \n");
printf("3:check Palindrome \n");
printf("0:Exit from Program \n");
scanf("%d",&ch);
switch(ch)

{
case 1:
{
printf("\nEnter the item to add in List: ");
scanf("%d",&item);
addNode(&list,item);
break;
}
case 2:
{
printf("Element in List are :\n");
showList(&list);
break;

}
case 3:
{
node res;
printf("\n The List is");
res=checkPalindrome(&list,list);
printf("Palindrome \n");
break;
}
case 0:
{
printf("\n Thanks for using this software");
break;
}
}


}while(ch!=0);

getch();
return 0;
}

I have an Issue on this:
how to stop and step out from recursion when required condition is met....?

Have a stack and a queue
Traverse the linked list and add every node to stack and to queue
Now, till the stack is empty,
check pop()==dequeue()
if there is a mismatch, say it is not a palindrome
if stack gets empty, then it is a palindrome

Here is a sample code.. I have assumed this with a String. Just we have to traverse the linked list instead of String in this code

import java.util.*;
class palin
{
public static void main(String []args)
{
Stack s=new Stack();
Queue q=new LinkedList();
String str="madam";
for(int i=0;i<str.length();++i)
{
s.push(str.charAt(i));
q.add(str.charAt(i));
}
while(!s.isEmpty())
{
if(s.pop()!=q.remove())
{
	System.out.println("Not a palindrome");
	System.exit(1);
}
}
System.out.println("palindrome");
}
}

Why not take this simple approach:

Step 1: Push the entire list in stack using a pointer ptr1.
Step 2: Take another pointer ptr2 and start iterating this pointer 1 step at a time to front.
Step 3: Start popping off the stack at the same time and compare the values (popped out value with the pointer's data)
Step 4: If this Linked List is a palindrome then these values should always match.

int isPal(node *tmp)
{
   static node *head = tmp;
   static int result =2;

   if(tmp->next) {
        result = isPal(tmp->next);
        if(!result) return 0;
        if(result==1) return 1;
   }

   if(tmp->val == head->val) {
      if( head == tmp || head->next == tmp) return 1;
      head = head->next; 
      return result;
   }
   else return 0;
}

just simply reverse the linked list ,it can be done in O(n) time.
then compare each node which is also O(n) time.
on the whole it takes O(2n),which is O(n) any way.

int checkpalindrome(struct node *root, struct node **left)
{
int ret;

if(root != NULL)
{
ret = checkpalindrome(root -> next, left);
if(root -> data != (*left) -> data)
return 0;
(*left) = (*left) -> next;
return ret;
}

return 1;
}

int checkpalindrome(struct node *root, struct node **left)
{
int ret;

if(root != NULL)
{
ret = checkpalindrome(root -> next, left);
if(root -> data != (*left) -> data)
return 0;
(*left) = (*left) -> next;
return ret;
}

return 1;
}

public boolean checkPalindrome(Node n)
{
char[] array = null;
int index = 0 ;

while(n.next != null)
{
array[index] = n.val;
index++;
n = n.next;
}

int i = 0 ;
int j = array.length - 1;

int lengthofArray = 0 ;

while (i<=j)
{
if(array[i] ! = array[j])
return false;
else
{
if(arrayLength%2 != 0)
{
if(i == j-2)
return true;
else
{
i++;
j--;
}

else
{
if( i == j -1 )
{
return true;
}
else
{
i++;
j--;
}
}
return false;
}




}

Here is how above code works
1. Build character array from linked list.
2. Start two pointers , one from the very first element of character array and other from end of the array.
3. Keep comparing corresponding elements.
4. return true if all the corresponding elements are equal , else return false.

1) Take two pointers, run second pointer twice as fast as first pointer.
2) when the fast pointer reaches the end of the list , the first pointer reaches the middle
3) calculate the sums of ascii values from start to mid and mid+ 1 to end
4) compare the two sums. if its same, that means its a palindrome.

Here is the code

int ispallindrome(LIST * node)
{
LIST *first,*second;
first = node;
second =node;
while (second !=NULL){
first=first->next;
second=second->next->next;
}

//first pointer will point to the middle of the list
LIST *trav;
int sum=0,sum1=0;
trav =node;
while (trav!=first){
sum += trav->value;
trav = trav->next;
}
//calculate the sum from mid+1 position till the end
trav = first->next;
while( trav!=NULL){
sum1 +=trav->value;
trav=trav->next;
}

if ( sum1 = sum)
return 1;
else
return 0;

}

this algo takes O(n)time

public static boolean listPalindromeCheck(LinkedList<Character> list)
    {
        int sz = list.size()/2;
        char[] arr1=new char[sz];
        ListIterator<Character> itr=list.listIterator();
        int i=0;
        for (i=0;i<sz;++i)
            arr1[i]=itr.next();
        if(list.size()%2>0)
            itr.next();
        for(--i;i>=0;--i)
        {
            if(arr1[i] != itr.next().charValue())
                return false;
        }
        return true;
    }

1. Treat Linked List a Stack Data Type.

foreach character in string
       if( the top of the stack is same as the present character)
             pop from stack
      else
             push character into stack 
       

    if stack isempty
       palindrome
    else 
      not palindrome

I have used Recursion to solve this prob:
here back pointer will start from last node and temp will start fetching nodes from start.

Please go through the code, You can also exe it... its working...!

#include<stdio.h>
#include<conio.h>
#include<malloc.h>

struct nodetype
{
int info;
struct nodetype *next;
};
typedef struct nodetype *node;

node createNode()
{
node n;
n=(node)malloc(sizeof(struct nodetype));
return n;
}

void addNode(struct nodetype **head,int in)
{
printf("1");
struct nodetype *temp,*add;
printf("2");


if(*head==NULL)
{
printf("3");
add=createNode();
printf("4");
add->info=in;
printf("5");
add->next=NULL;
printf("6");
*head=add;
printf("7");

}

else
{
temp=*head;
while(temp->next!=NULL)
{
temp=temp->next;
}
add=createNode();
add->info=in;
add->next=NULL;
temp->next=add;

}
}

void showList(struct nodetype **head)
{
node temp;
temp=*head;
if(*head==NULL)
{
printf("List is empty\n");
}
else
{

while(temp!=NULL)

{

printf("\nElement : %d",temp->info);
temp=temp->next;
}
}
}

node checkPalindrome(struct nodetype **head,struct nodetype *back)
{
node temp;
if(back->next!=NULL)
{
back=back->next;
temp=checkPalindrome(head,back);
}
if(back->next==NULL)
{
temp=*head;
}
if(back->info!=temp->info)
{

printf("\n not \n");
return temp;
}
temp=temp->next;
return temp;
}

int main()
{
int ch,item;

struct nodetype *list=NULL;

do
{
printf("\nPlease choose operation: \n");
printf("1:ADD an item \n");
printf("2:show the List \n");
printf("3:check Palindrome \n");
printf("0:Exit from Program \n");
scanf("%d",&ch);
switch(ch)

{
case 1:
{
printf("\nEnter the item to add in List: ");
scanf("%d",&item);
addNode(&list,item);
break;
}
case 2:
{
printf("Element in List are :\n");
showList(&list);
break;

}
case 3:
{
node res;
printf("\n The List is");
res=checkPalindrome(&list,list);
printf("Palindrome \n");
break;
}
case 0:
{
printf("\n Thanks for using this software");
break;
}
}

}while(ch!=0);

getch();
return 0;
}

1) Use the slow runner/fast runner technique. and use all the values slow runner is running through and add it to a stack. Also keep a counter to count the number of elements (Use the Fast runner to keep the count).
2)Follow this step only if the total count of the string is odd, else procedd to next step. Pop the first element in the stack.
3) Now use the slow runner and proceed one node to another. Compare the node's value with the last element popped. if they are same then proceed, else break.

int isPalindrome(struct node *head){
if(head->next == NULL){
return 1;
}
else
{
int isp;
struct node *left=head->next;
struct node *right = head->next;
isp = helperPalindrome(&left,right);
return isp;
}
}

int helperPalindrome(struct node **left, struct node *right){
int hisp;
if(right == NULL){
return 1;
}
else
{
hisp = helperPalindrome(left,right->next);
if(hisp == 1){
if((*left)->data == right->data){
*left=(*left)->next;
return 1;
}
else
return 0;
}
return 0;
}
}
done in o(1) space and o(1) time

What if we push the entire string into a stack and then pop it and see if the two strings are equal? What will be the time complexity of this approach?

1. create a char pointer
char *ptr;

2. traver the linked list and keep adding element to ptr to form a string

eg.
if our linked list is
c->a->t->a->c
then do as
*ptr = c;
*(ptr+1) = a;
*(ptr+2)=t;
...
.
.
*(ptr+5)='\0'; // ofcourse this would be a for loop
//so *(ptr+i) till node!=NULL

3. then again traverse linked list from starting and compare element from end of string ..
eg.. compare 1st node with * (ptr+n-1) // (ptr+n) is '\0';
.. compare 2nd node with * (ptr+n-2)
.. compare 3rd node with * (ptr+n-3)

and so on...

time complexity O(n)
space complexity o(1);

void pelindrome(node *h)
{
node *p;
int *stack=NULL;
int n=0,i;
for(p=h;p!=NULL;p=p->next)
{
stack=(int *)realloc(stack,sizeof(int));
*(stack+n)=p->data;
n++;
}
i=n/2;
for(p=h;i>=0;p=p->next,i--)
{
if(p->data != *(stack+i))
break;
}

if(i<n/2)
printf("it is not a pelindrome");
else
printf("it is a pelindorme");
for(i=0;i<25;i++)
printf("%d ",stack[i]);
}

/* Interview questions
*
* Author : touzzie
* mailto:tousifmt87@gmail.com
*/


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

#define TRUE 1
#define FALSE 0

typedef struct node
{
char st;
struct node *link;
}LIST_t;

typedef int BOOL;

LIST_t *head = NULL, *head2 = NULL;
LIST_t *pCur = NULL, *pPrev = NULL;


/*
* This function accepts multiword string from user
* and maintain it in a linked list.
*
* Implements linked list as QUEUE
*
* \param void
* \return void
*
*/

void createString(void)
{
char tmp;

printf("Enter the string(case sensitive) : ");
while((scanf("%c",&tmp)) && (tmp != '\n'))
{
pCur = (LIST_t *)malloc(sizeof(LIST_t));
pCur->st = tmp;

/* create first node */
if(NULL == head)
{
head = pCur;
pCur->link = NULL;
pPrev = pCur;
}
else
{
pPrev->link = pCur;
pPrev = pCur;
pCur->link = NULL;
}
}

}

#if 0
/*
* Display String
*
* \param void
* \return void
*
*/

void dispString(void)
{
LIST_t *ptr = head;

printf("String : ");
while(ptr != NULL)
{
printf("%c",ptr->st);
ptr = ptr->link;
}
printf("\n");

}

#endif

/*
* This funcion checks for palindrome
*
* \param void
* \return BOOL indicates palindrome or NOT
*
*/

BOOL checkPalindrome(void)
{
LIST_t *slwptr = head, *fstptr = head;
LIST_t *ptr1 = NULL, *ptr2 = NULL;
BOOL bContinue = TRUE;

/*
* Find the middle of linked list by fast runner/slow runner method
* slwptr Points to (n/2) + 1 when loop exits
*/

while((NULL != fstptr) && (FALSE != bContinue))
{
fstptr = fstptr->link;
if(fstptr != NULL)
{
fstptr = fstptr->link; /* Avoid chance of NULL pointer dereferencing */
slwptr = slwptr->link;
}
else
bContinue = FALSE;

}

/*
* create another list of length (n/2) and copy items from
* the middle of existing one.
* Implements SECOND linked list as STACK
*/

ptr2 = slwptr;
while(ptr2 != NULL)
{
pCur = (LIST_t *)malloc(sizeof(LIST_t));
pCur->st = ptr2->st;

/* create first node */
if(NULL == head2)
pCur->link = NULL;
else
pCur->link = pPrev;

pPrev = pCur;
head2 = pCur;
ptr2 = ptr2->link;

}

ptr1 = head;
ptr2 = head2;
bContinue = TRUE; /* Reset flag here */

/* Check the two linked lists */
while((NULL != ptr1) && (NULL != ptr2))
{
if(ptr1->st != ptr2->st)
{
bContinue = FALSE;
break;
}
ptr1 = ptr1->link;
ptr2 = ptr2->link;
}

return bContinue;

}


int main(void)
{
LIST_t *pCur = NULL, *pNext = NULL;
BOOL bCheck = FALSE;

createString();
// dispString();
if(NULL != head)
{
bCheck = checkPalindrome();
if(bCheck)
printf("PALINDROME\n");
else
printf("NOT PALINDROME\n");


/* free allocated memory */
/* free LIST 1 */
pCur = head;
while(pCur != NULL)
{
pNext = pCur->link;
free(pCur);
pCur = pNext;
}

/* free LIST 2 */
pCur = head2;
while(pCur != NULL)
{
pNext = pCur->link;
free(pCur);
pCur = pNext;
}
}
else
printf("You entered NULL string\n");
return 0;

}

->traverse input string from first to last element
-> create two linked lists
1. one insert element at head
2. other insert element at tail
-> check whether both the list are same or not.
-> if yes, palindrom else NOT!!!

copy the contents of the original list in reverse order into another linked list using recursion...then match the node values of original list and the new reversed list by taking two pointers...first for original list and second pointer for second(reversed) list by moving both pointers simultaneously one- one step....if somewhere the node values doesn't match then return and display the msg not a pallindrome....

public class Palindrome {
	static LinkedList head=null;
	public static void main(String[] args) {
			LinkedList list=LinkedListAddition.madelinkedList();
			head=list;
			if(isPalindrome(list))
				System.out.println("It is Palindrome");
			else
				System.out.println("It is not a Palindrome");
	}

	private static boolean isPalindrome(LinkedList list){
       boolean ret=false;
		if(list.link==null)
		{
			ret=list.data.equalsIgnoreCase(head.data);
	}
		else{
			ret= isPalindrome(list.link) && list.data.equalsIgnoreCase(head.data);
		}
		head=head.link;
		return ret;
	}

}

1. Get the length of the link list.
2. Push the nodes of the list to stack from beginning till length/2.
3. Pop-up from stack & keep comparing till end of the list from length/2+1.

#include<stdio.h>

struct node
{
char a;
struct node *link;
};
void add(struct node**a,char ab)
{
struct node *temp,*r;
temp=*a;

if(*a==NULL)
{
temp=malloc(sizeof(struct node));
temp->a=ab;
temp->link=NULL;
*a=temp;
}
else
{
temp=*a;
while(temp->link!=NULL)
{
temp=temp->link;
}
r=malloc(sizeof(struct node));
r->a=ab;
temp->link=r;
r->link=NULL;

}
}
void palindrome(struct node *a)
{
struct node *temp,*mid;
int i,flag=0;
mid=a;
temp=a;
int count=0;
while(a!=NULL)
{
count++;
a=a->link;
}

int p=(count)/2;
for(i=0;i<p;++i)
{
mid=mid->link;
}


for(i=0;i<p;++i)
{
if((mid->a)==(temp->a))
{
flag=0;
}
else{flag=1;}

mid=mid->link;
temp=temp->link;
}
if(flag==0)printf("the string is palindrome ");
else
printf("the string is not palindrome ");
}


void main()
{
struct node *p;
p=NULL;

add(&p,'m');
add(&p,'a');
add(&p,'d');
add(&p,'a');
add(&p,'m');

palindrome(p);

}

1.find the number of nodes in the node.
2.now design a function to get the kth element from end.
3.now compare kth element from start and kth element from end till middle is reached.

package com.sample.que.linkedlist;

public class PalindromeLL {

	Node head;

	int counter;

	public void addData(char data) {

		Node newNode = new Node(data);

		Node currentNode = head;

		if (currentNode == null) {
			head = newNode;
			counter++;
			return;
		}

		while (null != currentNode.next) {
			currentNode = currentNode.next;
		}
		currentNode.next = newNode;
		counter++;
		return;
	}

	public char getNode(int index) {
		if (index < 0) {
			return '\0';
		}

		Node currentNode = head;

		for (int i = 0; (i < index && currentNode != null); i++) {
			currentNode = currentNode.next;
		}
		System.out.println("\n");
		return currentNode.data;

	}

	public int getNodeCount() {
		return counter;
	}

	public boolean isPalindrome() {
		int i = 0;
		int j = getNodeCount() - 1;

		boolean checkPalin = false;

		while (i <= j) {
			if (getNode(i) == getNode(j)) {
				checkPalin = true;
			}else{
				checkPalin = false;
				break;
			}

			i++;
			j--;
		}
		return checkPalin;
	}

}

package com.sample.que.linkedlist;

public class PalindromeLL {

	Node head;

	int counter;

	public void addData(char data) {

		Node newNode = new Node(data);

		Node currentNode = head;

		if (currentNode == null) {
			head = newNode;
			counter++;
			return;
		}

		while (null != currentNode.next) {
			currentNode = currentNode.next;
		}
		currentNode.next = newNode;
		counter++;
		return;
	}

	public char getNode(int index) {
		if (index < 0) {
			return '\0';
		}

		Node currentNode = head;

		for (int i = 0; (i < index && currentNode != null); i++) {
			currentNode = currentNode.next;
		}
		System.out.println("\n");
		return currentNode.data;

	}

	public int getNodeCount() {
		return counter;
	}

	public boolean isPalindrome() {
		int i = 0;
		int j = getNodeCount() - 1;

		boolean checkPalin = false;

		while (i <= j) {
			if (getNode(i) == getNode(j)) {
				checkPalin = true;
			}else{
				checkPalin = false;
				break;
			}

			i++;
			j--;
		}
		return checkPalin;
	}

}