yeah a[i] == a[n-i] will work if you know the length of the list in advance.
What if we dont know the length in advance. One has to to make two passes on
a list ,first to find the length or midpoint and another pass for
comparison.
Can we do it in a single pass?
On Tue, Sep 8, 2009 at 9:01 PM, ankur aggarwal <ankur.mast....@gmail.com>wrote:
> @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;
>> >
>> > }
>>
>>
>>
>
> >
>
--
<<Bharath>>
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
