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 <[email protected]> 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 [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
