DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 5 of 5

Thread: linked list - palindrome

  1. #1
    Join Date
    Jul 2007
    Location
    bangalore
    Posts
    16

    linked list - palindrome

    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.

    hope i will get answer from experts here. thanks in advance.

  2. #2
    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. #3
    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. #4
    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. #5
    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
    DKyb
    -------------------------------
    Life is a short warm moment -
    Death is the long cold rest.
    Pink Floyd
    -------------------------------

Similar Threads

  1. single linked list.. so confused...
    By zaacze in forum Java
    Replies: 3
    Last Post: 04-01-2007, 06:15 PM
  2. Linked List Error
    By Dark Rain in forum C++
    Replies: 11
    Last Post: 02-18-2007, 01:06 PM
  3. Replies: 1
    Last Post: 11-04-2005, 07:19 AM
  4. Problem with linked lists and iterators
    By white94cam in forum C++
    Replies: 2
    Last Post: 03-31-2005, 12:02 AM
  5. EMERGENT.... double linked list
    By mary in forum Java
    Replies: 0
    Last Post: 07-20-2001, 08:42 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center