CareerCup

first find the mid of linked list by traversing with 2 ptrs ie. ptr1 and ptr2 ptr1 will increment to next node and ptr2 will increment 2 nodes ahead by this way we will reach at the mid now start 2 diff ptr in backward direction till not reach start and end. and check the value in node is equal or not.

first find the mid of linked list by traversing with 2 ptrs ie. ptr1 and ptr2 ptr1 will increment to next node and ptr2 will increment 2 nodes ahead by this way we will reach at the mid now start 2 diff ptr in backward direction till not reach start and end. and check the value in node is equal or not.

my poly algo is suffer the test case : 846348
can any one tell me how to the solve this problem in my algo?

my algo is working for perfect values like polyndrome:85458 and non-polyndrome:597643


1.form the linked list,in struct node *p
my structure is, 
struct node
{
       int data;
       struct node *link;
       }*p,*m;
1.1 After forming the linked list,
2.copy the list into another struct pointer ,struct node *m, m=p;
3.reverse the linked list,using reverse algo pass the argument as p;
4.reverse algo
reverse()
{  
    struct node *q,*r,*s;
    q=p;
    r=NULL;
    while(q!=NULL)
    {
         s=r;            
         r=q;
         q=q->link;
         r->link=s;
         }
    p=r;
    }
5.check the linked list m and p to find  polyndrome or not 
6.polyndrome algo
poly()
{
      int flag;
      while(m!=NULL)
      {
          if(m->data==p->data)
          {
             flag=0;
             m=m->link;
             p=p->link;
             }
          else
          {
              flag=1;
              break;
              }
           }
      if(flag==1)
          printf("\n\nThe given linked list is not a polyndrome\n\n");
      else
          printf("\n\nThe given linked list is a polyndrome\n\n");
          }

we can solve this problem with fast and slow pointer concept

public boolean isPalindrome(Node head)
{
	Node slwptr=head;
	Node fstptr=head;
	Stack<int> s1=new Stack<int>();
	while(fstptr!=null && fstptr.next!=null)
	{
		s1.push(slwptr.data);
		slwptr=slwptr.next;
		fstptr=fstptr.next.next;
	}
	if(fstptr!=null)
		slwptr=slwptr.next;
	while(slwptr!=null)
	{
		if(slwptr!=s1.pop())
			return false;
	}
	return true;
}

we can solve this problem with fast and slow pointer concept

public boolean isPalindrome(Node head)
{
	Node slwptr=head;
	Node fstptr=head;
	Stack<int> s1=new Stack<int>();
	while(fstptr!=null && fstptr.next!=null)
	{
		s1.push(slwptr.data);
		slwptr=slwptr.next;
		fstptr=fstptr.next.next;
	}
	if(fstptr!=null)
		slwptr=slwptr.next;
	while(slwptr!=null)
	{
		if(slwptr!=s1.pop())
			return false;
	}
	return true;
}

If there's no restrictions on memory, maybe we can just find the length of the list, and push the first half of the list into a stack.
Then navigate to the middle of the list, and start comparing what you pop from the list with what is in the list.