CareerCup

int Palindrome(node *p){
     static node *head=p;
     static int result=2;
     if(p){
            result=Palindrome(p->next);
            if(result==0||result==1) return result;
            if(head->data==p->data){
                      if(head==p||head->next==p) return 1;
                      head=head->next;
             }else return 0;
     }
  return result;
}

WAP stands for what ?

wap = write a program?

<pre lang="" line="1" title="CodeMonkey45706" class="run-this">bool check(list<char>& lst,list<char>::iterator traverse, list<char>::iterator itr,list<char>::iterator& itr1);
int main()
{
//Check whether linked list is a palindrome
list<char> lst;
cout<<"Enter the number of elements ";
int num;
cin>>num;
cout<<"Enter the characters ";
for(int i=0;i<num;++i)
{
char val;
cin>>val;
lst.push_back(val);
}
list<char>::iterator itr=lst.begin();
if(num == 1)
{
cout<<"It is a palindrome\n";
exit(0);
}
for(int i=0;i<num/2-1;++itr,++i);
list<char>::iterator itr1=itr;
++itr1;
if(num%2)
++itr1;
if(check(lst,lst.begin(),itr,itr1))
cout<<"Palindrome\n";
else
cout<<"Not a palindrome";
}

bool check(list<char>& lst,list<char>::iterator traverse, list<char>::iterator itr,list<char>::iterator& itr1)
{
if(traverse != itr)
{
list<char>::iterator tempItr = traverse;
if(!check(lst,++tempItr,itr,itr1))
return false;
}
if(*traverse != *itr1)
return false;
++itr1;
return true;
}</pre><pre title="CodeMonkey45706" input="yes">
</pre>

Hope it is double-link list, otherwise.

<pre lang="" line="1" title="CodeMonkey93390" class="run-this">public boolean isPalindrome(Node head) {
if (head.next == null) {
return true;
}

Node prev = null, current = head;
while (current.next != null) {
prev = current;
current = current.next;
}

if (head.value != current.value)
return false;

if (head.next == current)
return true;

prev.next = null;
return isPalindrome(head.next);
}</pre><pre title="CodeMonkey93390" input="yes">
</pre>

Find the middle element in the list. Reverse all elements after the middle element

Please check my code:

int ispalindromeEFF(node* head)
{
	if(head==NULL)
	{
		return 0;
	}
	node *xq,*y,*p,*r;
	int flag=1;
	p=NULL;
	xq=head;
	r=xq->link;
	y=head;
	
	while(y->link && y->link->link)
	{
		y=y->link->link;
		//reverse
		xq->link=p;
		p=xq;
		xq=r;
		if(r)
		{
			r=r->link;
		}
	}
	if(y->link) //even length
	{
		xq->link=p;
		p=xq;
		xq=r;
		r=r->link;
		y=xq;
	}
	else
	{
		y=r;
	}
	node *temp;
	temp=p;
	p=xq;
	xq=temp;
	if(xq)
	{
		r=xq->link;
	}
	while(y)
	{
		if(y->data != xq->data)
		{
			flag=0;
		}
		y=y->link;
		xq->link=p;
		p=xq;
		xq=r;
		if(r)
		{
			r=r->link;
		}
	}
	return flag;
}

Feedbacks are welcome

LinkedList* LinkedList::IsPalindrom(LinkedList *cur, LinkedList *head)
{
if(cur == NULL)
return NULL;
LinkedList *temp = NULL;
if(cur->next != NULL)
temp = IsPalindrom(cur->next, head);
else
temp = head;
if(temp == NULL)
return NULL;

if(cur->data == temp->data)
if(cur == head)
return temp;
else
return temp->next;
else
return NULL;
}

Call Like this

if(list->IsPalindrom(list, list) == NULL)
{
cout << "Not Palindrom " << endl;
}
else
cout << "Yes Palindrom " << endl;


You cant get better solution than this :)

What is mean by Palindrome?

node *
traverse_to_list_mid(node *n);

int
palindrome (node  **first, node *last)
{
    if (last == NULL)
        return 1;

    ret = palindrome (first, last->next);
    if (ret == 0)
        return 0;

    if ((*first)->data == last->data) {
        (*first) = (*first)->next;
        return 1;
    } else {
        return 0;
    }
    return 0;
}

int
main ()
{
    node *first, *last;
    last = traverse_to_list_mid (first);
    ret = palindrome (&first, last);
    if (ret == 0)
        printf ("not a palindrome");
    else 
        printf ("Palindrome");
}

Add all the elements to a stack...
On the next traversal, compare elements in the stack with the elements in the list...

Time Complexity = Space Complexity = O(n)