Interview Question
Country: India
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");
}
That implied your non-polydrome test case did not work. I think the param of the reverse function need two ptr like Node** p
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;
}
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.
- dabbcomputers February 29, 2012