@barath
u r using extra space..
wat is new about this sol
change to array..
then do as simple
using a[i]==a[n-i] ???
On Tue, Sep 8, 2009 at 8:04 PM, Bharath <bharath1...@gmail.com> wrote:
>
> Q: Check whether given singly linked list is palindrome or not in
> single pass.
>
> Instead of making two passes, can we do it in single pass on a list?
>
> One method i can think of is, hashing character to its postion and
> check for the sum.
>
> abccba
> 123456
>
> a: 1+6=7
> b: 2+5=7
> c: 3+4=7
>
> On Sep 8, 5:33 pm, ankur aggarwal <ankur.mast....@gmail.com> wrote:
> > for 1st
> >
> > use hare and tortoise algo to find the mid point of the linklist ...
> > and reverse the other end
> >
> > like
> >
> > a->b-->c->d->v->u
> > a->b-->c<-d<-v<-u
> >
> > pointer 1 will point to a and other pointer will point to u
> > then it is done ..
> >
> > u can check..
> >
> > 2nd
> >
> > for(p = original; p != null; p = p->next->next)
> > p->next->random = p->random->next;
> >
> > (i) insert one new node in original list for every node .
> >
> > (ii) then change "random" links of newly inserted nodes
> > i.e; for every new node (p->next)
> > p->next->random = p->random->next
> >
> > (iii)then split 2 lists
> >
> > Now Split the Lists
> >
> > code is
> >
> > for( q =original->next,r = original->next,p = original; p != null; p =
> > p->next,q=q->next)
> > { p->next = p->next->next;
> > q->next = q->next->next;
> >
> > }
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
