Sereche

 Profile Answers by Sereche 

• Jul 8th, 2012

 

The fastest way to do this is to traverse the linked list forward once, saving the value at each node (or a pointer to the node) in a backwards-traversable data structure. If you know the size of the list beforehand, an array would be most efficient; otherwise, a dynamic array is probably best. You could then iterate through this structure in reverse order efficiently, printing the value at each node.

If memory usage is a concern (i.e., your system might not have enough memory to save the address to every node), your best bet is a divide-and-conquer approach. Since you most likely wont have that many items, I wont go into further detail here (and if you do, I would strongly urge you to consider a different data structure, as well as refraining from printing out every entry).

I dont understand the constraint regarding the head pointer; the list should not be modified in any way by a program that only prints its contents.