There may be ways to do this more efficiently, based on the specific properties of LinkedLists. But the chance that this will actually matter, at all, is very small. The time it takes to print the entries will be significantly longer than the time it takes to reverse, so keep the code as simple as possible. There's no benefit in trying to be fancy here. If the interviewer sounds like he really wants the most efficient algorithm possible, regardless of how unnecessary it may be, then I'd try:
Now since you say "the size is not known" it's possible you mean a linked list that is not a LinkedList. Because the size of a LinkedList is known. If we're leaving out the standard Java collections entirely, that makes things a little more challenging. For a singly-linked list I'd just create a new linked list. Iterate through the original list and add each entry to the start of the new list. If memory is tight you can remove each entry from the original list as you go. Then iterate through the second list, printing as you go. [ February 11, 2004: Message edited by: Jim Yingst ]
I think they're probably not talking about LinkedLists in Java but the datastructure. They're trying to see how you think. I would say something like : If the linked list is doubly linked (like in Java) the answer is trivial. A simple solution is to iterate through the list putting each item on a stack. Then print the stack. This would not be effecient if the list is very large. To actually reverse the list, you can iterate through the list and reverse the linkages. Then print out the new list. D.
Hi, If we donot know the size, may be we can go for a recursive solution. Consider an implementation of the linked list data structure. Let us say we have a method printList() which is supposed to print the elements in reverse order.
Where print method will just print the current node information. I am not sure about the performance of this approach as compared to the other approaches. Thanks, Basu.
Basudev, nice solution! Of course it's quite similar to Don's using a stack - after all, you are just using the method call stack...
The soul is dyed the color of its thoughts. Think only on those things that are in line with your principles and can bear the light of day. The content of your character is your choice. Day by day, what you do is who you become. Your integrity is your destiny - it is the light that guides your way. - Heraclitus
As nice as recursion is, I would actually avoid recusive data structure calls in stack-based languages* unless you can be confident that stack space required won't be a problem. There's nothing stopping you from creating a linked list with a few million elements, but recursion will stop you from being able to print it out. * Exception: if the last action of a method is to call itself, so-called "Tail Recursion," then some compilers/languages will reduce it to an iterative form that uses no stack space