For the first question
*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.*
I can think of a recursive solution.
@bharath
apply your logic at
"abbaabba"
show me your steps
On Tue, Sep 8, 2009 at 8:04 PM, Bharath 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
@bharath
how will u recognize
which "a" to compare to which "a"
or apply on "malayalam"
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegr
Are we able to store the incoming characters?
On Tue, Sep 8, 2009 at 11:51 AM, Bharath wrote:
>Slightly modifying first question.
>
>Check whether a string is palindrome in single pass.
>
>Meaning an online algorithm is required, i.e. it must be able to read
>one character at a time from a stre
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,
@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 wrote:
>
> Q: Check whether given singly linked list is palindrome or not in
> single pass.
>
> Instead of making two passes, can we do it
1st ques
struct Node
{ datatype DATA
struct Node * next;
struct Node * random;
};
struct Node * cloneList(Node * original)
{
struct Node *p,*q,*r;
for(p = original; p != null; p = p->next->next)
{
q = p->next;
p->next = getNewNode();
p->next->next = q;
}
for(p = origin
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,
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
@bharat
your statement is not clear..
On Tue, Sep 8, 2009 at 11:51 AM, Bharath wrote:
>
> Slightly modifying first question.
>
> Check whether a string is palindrome in single pass.
>
> Meaning an online algorithm is required, i.e. it must be able to read
> one character at a time from a stream
Slightly modifying first question.
Check whether a string is palindrome in single pass.
Meaning an online algorithm is required, i.e. it must be able to read
one character at a time from a stream and tells whether string read so
far is palindrome or not.
--~--~-~--~~~---
well the 2nd ques is not clear.
can u explain it in simpler manner
On Wed, Aug 12, 2009 at 4:37 PM, Aravind Narayanan wrote:
>
> On Wed, Aug 12, 2009 at 10:38, varun bhatia wrote:
>
>> 1. Given a single link list with one info part containing single character
>> and a
On Wed, Aug 12, 2009 at 10:38, varun bhatia wrote:
> 1. Given a single link list with one info part containing single character
> and a link. Check whether the link list is a palindrome or not.
> The algo should run in Linear time only. You can't use any array or string
> to store the string of li
13 matches
Mail list logo