DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

1. Registered User
Join Date
Jul 2007
Location
bangalore
Posts
16

recently my friend had been to C++ interview. i would like to post one question here for solution. the question is

we have a single linked list and u dont know how many nodes are there in the list.
without using any temporary data structure we have to check whether the linked list is palindrom or not.?

palindrom means if we reverse the list, the reversed one will be same as original one.

2. Senior Member
Join Date
Dec 2003
Posts
3,366
crude, but this should do it:

1) traverse the list once to find its length
2) grab a pointer to the middle node (deal with even or odd number of nodes)
3) by ugly brute force you can now compare the two "sub lists". Traverse all the way to the end of the second half, and compare that to the first element in the top half. Repeat for next to last and second, ... if the number of nodes was odd ignore the middle element and if even your final compare works. Abort when you find the first unmatched set, if never find one, it is indeed a palindrome.

You must take care not to goof up the sub lists because they are just pointers inside the one list, you cannot rely on "null" terminated lists but must use the count of nodes carefully instead.

3. Registered User
Join Date
Jul 2007
Location
bangalore
Posts
16
Is there any way to know whether single linked list is palindrome in single pass...

it means without coming back to linked list ..in single traversing we should able to check whether the list is palindrome or not..including conditions stated in 1st post... plz help me in this..thanks to all..

4. Registered User
Join Date
May 2007
Posts
843

3) by ugly brute force you can now compare the two "sub lists". Traverse all the way to the end of the second half, and compare that to the first element in the top half. Repeat for next to last and second, ... if the number of nodes was odd ignore the middle element and if even your final compare works. Abort when you find the first unmatched set, if never find one, it is indeed a palindrome.
I not very understand what u say here but as far as i know.

I will try traverse from first half and end of second half which means
ptr to a ptr to f
abcd cdef

If ptr to a == ptr to f that is palindrome.
I understand u said abort when first comparison is unmatched.

A billion thanks for your help.

5. Registered User
Join Date
Jan 2005
Location
UK
Posts
604
To be honest: I do not believe there is a way to check a single list list for palindrome-ness in 1) only one iteration *AND*2) not using a temporary structure. If either one of these conditions is negated the solution is easy.

But the next best thing with the same complexity (O(N)) is an algorithm that traverses the list a total of 3 times.
1. traverse: 2 pointers (p1,p2) initially on the start of the list. whenever you advance p2 for 2 positions, advance p1 for 1 position. when p2 is at the end, p1 is at the middle of the list (+/- 1, I leave you with the gory details!)

2. traverse (1/2 traverse): reverse the second half of the list. (A little problem in itself, but do-able in 1 iteration, using 3 pointers)

3.traverse: compare the two 1/2 lists: they should have the elements in the same order, if the original list was a palindrome

4. traverse (1/2 traverse): reverse the second list back to its original order and append it to the first half list returning the original list.

This algorithm has to traverse the list a total of 3 times so its complexity is O(N). The overhead for this algorithm is about 10 operations per iteration (pessimistic) so not too bad. If you need higher performance, use a different container. For palindrome-tests only, vector should be the best suited, because you can address the elements by simple arithmetic calculations...

Hopefully that was not too cryptic?!

Cheers,

D

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise