Re: Palindrome in Linked list

From: Willem (willem_at_stack.nl)
Date: 01/24/05 

Date: Mon, 24 Jan 2005 15:29:33 +0000 (UTC)

CTips wrote:
) Can you do it in O(n) using O(1) memory? I don't think you can do it
) efficiently using recursion.

Of course recursion is efficient, you're basically using the stack as O(n)
extra memory. Note that the recursion is linear.

And about O(n) time and O(1) memory: Are you allowed to alter the
linked list ? If not, I doubt it can be done within those restraints.
(Assuming it's singly linked, of course. Doubly linked is easy.)

SaSW, Willem 

-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT