Print immutable linked list in reverse
November 29, 2022
linked-list stackProblem URL: Print immutable linked list in reverse
We can use a stack to store the values of the linked list. We will then pop the values from the stack and print them.
# """
# This is the ImmutableListNode's API interface.
# You should not implement it, or speculate about its implementation.
# """
# class ImmutableListNode:
# def printValue(self) -> None: # print the value of this node.
# def getNext(self) -> 'ImmutableListNode': # return the next node.
class Solution:
def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None:
stack = []
while head:
stack.append(head)
head = head.getNext()
while stack:
stack.pop().printValue()
Time complexity: O(n)
, n is the number of nodes in the linked list
Space complexity: O(n)
We can achieve the same result using recursion.
class Solution:
def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None:
if head:
self.printLinkedListInReverse(head.getNext())
head.printValue()