Print linkedlist reversely

Question

I'm working on the problem of print a linked list reversely without destruction. I'm wondering if any other better ideas, in terms of both time complexity improvement and space complexity improvement. I also welcome for code bugs and code style advice.

class LinkedListNode:
 def __init__(self, value, nextNode):
 self.value = value
 self.nextNode = nextNode
 def print_reverse(self):
 if not self.nextNode:
 print self.value
 return
 else:
 self.nextNode.print_reverse()
 print self.value
if __name__ == "__main__":
 head = LinkedListNode('a', LinkedListNode('b', LinkedListNode('c', LinkedListNode('d', None))))
 head.print_reverse()

• Lin Ma: Is anyone have advice to print a linkedlist reversely, without recursively and have less time complexity/less additional space complexity, it will be great. :)
• Tolani: This could be done iteratively. You have to keep track of three variables previous, current and next. You can have a while loop that checks for if node.next != null and in that same loop, you can change the next to previous and previous becomes current etc. I can't write a review, sorry can't code in Python.
• Lin Ma: @TolaniJaiye-Tikolo, thanks and vote up. I think about your method today and a bit lost how do you move backward? Since linked-list only record forward? If you have any pseudo or real code, it will be great.

Answer 1

Code Style notes:

• follow PEP8 style guide, in particular:
  • one empty between the class methods
  • two empty lines after the class definition and before the next block
• use print() function instead of a statement - this way you are staying compatible with the Python 3.x
• rename nextNode to next_node
• don't forget about the docstrings

Other improvements:

• you should probably explicitly inherit from object to have a new-style class (reference)
• instead of a print_reverse(), how about you create a generator method that would yield nodes instead of printing - this can come out handy later when you would actually need to use the node values, not just have them on the console

With all the suggestions applied (except the docstrings):

class LinkedListNode(object):
 def __init__(self, value, next_node):
 self.value = value
 self.next_node = next_node
 def reverse_traversal(self):
 if not self.next_node:
 yield self.value
 else:
 for node in self.next_node.reverse_traversal():
 yield node
 yield self.value
if __name__ == "__main__":
 head = LinkedListNode('a', LinkedListNode('b', LinkedListNode('c', LinkedListNode('d', None))))
 for node in head.reverse_traversal():
 print(node)

---

As a side note, if you would be on Python 3.3+, this part:

for node in self.next_node.reverse_traversal():
 yield node

can be rewritten using the generator delegation:

yield from self.next_node.reverse_traversal()

• Lin Ma: Thanks alecxe, do you have any other new ideas to print a linkedlist reversely, without recursive method call and have less time complexity/less additional space complexity?
• alecxe: @LinMa well, one general idea is to traverse it forward, put items on stack and then just read from it. Forward traversal can be done in a simple while current_node loop. I'm though very far from being an expert in algorithms, very rusty at this point. Thanks.
• Lin Ma: Thanks alecxe, vote up, but space complexity is the same (which is O(n)), correct?
• alecxe: @LinMa yup, but requires extra memory for the stack. Thanks.