4
\$\begingroup\$

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()
\$\endgroup\$
3
  • \$\begingroup\$ Is anyone have advice to print a linkedlist reversely, without recursively and have less time complexity/less additional space complexity, it will be great. :) \$\endgroup\$ Commented Dec 22, 2016 at 6:37
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Dec 22, 2016 at 9:45
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Dec 25, 2016 at 21:24

1 Answer 1

Reset to default
6
\$\begingroup\$

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()
\$\endgroup\$
4
  • \$\begingroup\$ 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? \$\endgroup\$ Commented Dec 22, 2016 at 6:38
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Commented Dec 22, 2016 at 7:05
  • \$\begingroup\$ Thanks alecxe, vote up, but space complexity is the same (which is O(n)), correct? \$\endgroup\$ Commented Dec 25, 2016 at 21:24
  • 1
    \$\begingroup\$ @LinMa yup, but requires extra memory for the stack. Thanks. \$\endgroup\$ Commented Dec 25, 2016 at 21:57

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.