We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Print Immutable Linked List in Reverse

Number: 1404

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given an immutable linked list, print out all node values in reverse order. You are provided with only two APIs: • ImmutableListNode.getNext() to retrieve the next node, and
• ImmutableListNode.printValue() to print the current node’s value. You cannot modify the linked list, so you must use one of the allowed methods to achieve the reverse order printing.

Key Insights

  • The linked list is immutable, preventing any in-place modifications.
  • Recursion naturally leverages the call stack to achieve a reverse order of operations.
  • An iterative approach using an explicit stack is also a valid solution.
  • The challenge constraints lead to O(n) time complexity with O(n) extra space for both recursive and stack-driven solutions.

Space and Time Complexity

Time Complexity: O(n) for traversing the list once
Space Complexity: O(n) due to the usage of the call stack in the recursion or an explicit stack
(Note: Constant space solutions are not applicable due to the immutability constraint.)

Solution

We solve this problem by utilizing either a recursive approach or an iterative approach with an explicit stack. In the recursive method, we traverse the linked list until the end and then print the nodes during the backtracking phase. This effectively prints the list in reverse order. Alternatively, we can traverse the list iteratively, pushing each node onto a stack, and then pop them to print in reverse order. Both methods satisfy the problem's requirements using only the provided API.

Code Solutions

# Recursive solution to print the immutable linked list in reverse order
def printLinkedListInReverse(head):
    # If the head is None, we've reached the end of the list.
    if head is None:
        return
    # Recursively call the function with the next node.
    printLinkedListInReverse(head.getNext())
    # After returning from recursion, print the current node's value.
    head.printValue()

# Iterative (stack-based) solution to print the immutable linked list in reverse order
def printLinkedListInReverseStack(head):
    stack = []
    current = head
    # Traverse the list and push each node onto the stack.
    while current:
        stack.append(current)
        current = current.getNext()
    # Pop nodes from the stack and print their values to achieve reverse order.
    while stack:
        node = stack.pop()
        node.printValue()
← Back to All Questions