CODEWITHSUNDEEP
pythonalgorithmpython-2.7linked-list
Lin Ma
Lin Ma

Reputation: 10139

Print linkedlist reversely

I'm working on the problem of print a linked list reversely without destruction. My specific questions are,

  1. wondering if any other better ideas, space complexity improvement, my current space complexity is O(n) using recursive call stack;
  2. wondering any ideas to improve algorithm time complexity?

BTW: If there are anything wrong with my current code, like logical bugs, please feel free to advise.

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()

Upvotes: 1

Views: 109

Answers (3)

Matt Timmermans
Matt Timmermans

Reputation: 59184

Using O(n) space to print the list in reverse is not very nice, especially if that's stack space.

If you can't modify the list, then you can do it in O(log N) space and O(N log N) time like this:

class LinkedListNode:
    def __init__(self, value, nextNode):
        self.value = value
        self.nextNode = nextNode

def count(list):
    ret=0
    while list:
        ret+=1
        list=list.nextNode
    return ret

def print_reverse(list,size=-1):
    if size<0 and list:
        size=count(list)

    while size>1:
        midpoint=size/2
        tail=list
        for _ in xrange(midpoint):
            tail=tail.nextNode
        print_reverse(tail,size-midpoint)
        size=midpoint
    if size>0:
        print list.value


head = tail = LinkedListNode(1,None)
for n in range(2,29):
    tail.nextNode=LinkedListNode(n,None)
    tail=tail.nextNode

print_reverse(head)

Upvotes: 0

smddzcy
smddzcy

Reputation: 443

If your LinkedListNode's are not immutable and you are only concerned about the final structure of the linked list, you can reverse the linked list in one iteration, and print the elements while re-reversing it from the end in another iteration; which gives you Ө(1) space complexity and Ө(n) time complexity.

Otherwise, if you are not allowed to change any structure at any point, I think Ө(n) space is the best you can get.

Here is a Java implementation:

class LinkedListNode {
    int data;
    LinkedListNode next;
    LinkedListNode(int data) { this.data = data; }
}

class LinkedListReversePrintImplementation {
    static void printReversely(LinkedListNode node) {
        LinkedListNode currNode = node,
                       nextNode = node.next,
                       temp;

        // Remove the link from first node
        currNode.next = null;

        // Reverse the other links
        while (nextNode != null) {
            temp = nextNode.next;
            nextNode.next = currNode;
            currNode = nextNode;
            nextNode = temp;
        }

        // `currNode` now contains the last node
        // Initialize the `nextNode` of the reversed linked list
        nextNode = currNode.next;

        // Remove the first link again
        currNode.next = null;

        // Print the last node
        System.out.println(currNode.data);

        // Print the other nodes while re-reversing it
        while (nextNode != null) {
            System.out.println(nextNode.data);

            temp = nextNode.next;
            nextNode.next = currNode;
            currNode = nextNode;
            nextNode = temp;
        }
    }
}

Upvotes: 2

AChampion
AChampion

Reputation: 30268

Your print_reverse() can be simplified to:

def print_reverse(self):
    if self.nextNode:
        self.nextNode.print_reverse()
    print(self.value)

I don't see how you can improve this, you will need a stack of some description because this list is not doubly linked. But you can use your own stack, which would avoid the risk of recursion overflow:

def print_reverse(self):
    stack = [self]
    nextNode = self.nextNode
    while nextNode:
        stack.append(nextNode)
        nextNode = nextNode.nextNode
    while stack:
        print(stack.pop().value)

Upvotes: 2

Related Questions