Jim Battle wrote:
If memory is tight and nobody else is using the list,
flip the pointer
direction as you go down the list. When you hit the end, print it out,
follow the pointers back to the beginning, flipping them back again.
Yep.
Or perhaps the singly linked list already stores the
XOR of the forward
and back pointers and so no flipping is necessary.
Which hints at what Eric offered up:
I think the correct answer to Chris's question is
to ask whether the
reverse access is a one time thing, or if it's a significant enough
change to the software spec that the list should be doubly linked.
The amazing thing is that well north of 90% of candidates don't bother
to ask questions that would help them identify the most appropriate
solution to the problem. The typical approaches are to repeatedly
iterate, to recurse or to use an explicit stack (which is materially the
same thing). Questions like "can I modify the list?" or "Is there
anything that precludes changing the spec to make this a doubly-linked
list" are rarely posed -- and when they are, I know I've got a keeper.
The most tortured solution offered to date was the one where the guy
proposed to create a doubly-linked list that contained pointers to nodes
of the original list...
--
Chris Kennedy
chris at
mainecoon.com AF6AP
http://www.mainecoon.com PGP KeyID 108DAB97
PGP fingerprint: 4E99 10B6 7253 B048 6685 6CBC 55E1 20A3 108D AB97
"Mr. McKittrick, after careful consideration..."