Print a singly-linked list backwards, in constant space and linear time

Question

I heard an interview question:

"Print a singly-linked list backwards, in constant space and linear time."

My solution was to reverse the linkedlist in place and then print it like that. Is there another solution that is nondestructive?

Answer 1

You've already figured out most of the answer: reverse the linked list in place, and traverse the list back to the beginning to print it. To keep it from being (permanently) destructive, reverse the linked list in place again as you're traversing it back to the beginning and printing it.

Note, however, that this only works if you either only have a single thread of execution, or make the whole traversal a critical section so only one thread does it at a time (i.e., a second thread can never play with the list in the middle of the traversal).

Answer 2

If you reverse it again after printing it will no longer be destructive, since the original order is restored.

Answer 3

You could use a recursive call down the linked list chain with a reference to what you wish to write to. Each node would use the child node's print function while passing the reference before printing itself.

That way each node in the list would pass down, until the last one couldn't and would go straight to the write, then each one back up the chain would write after the last all the way back up to the front.

Edit

This actually doesn't fit the specs because of the linear space on stack. If you had something outside to walk the functions and a method of writing to the front of a string the base logic can still work though.

Answer 4

Okay , this could be an interview question , but it is actually a question behind weis algorithms book. The question clearly states that we cannot use recursion (something the interviewer will hide and reveal later on) as recursion will not use constant space, moslty recursion will become a major point of discusion going forward. Solution is reverse print and reverse back.