@bharath apply your logic at "abbaabba" show me your steps
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 -~----------~----~----~----~------~----~------~--~---