⚡Flashcard Drill➔
NeetCode #314LC-1265MediumLinked ListNC Algo100
← Back to All Problems

#314 · #1265 · Print Immutable Linked List in Reverse(逆序打印不可变链表)

📌 Problem Statement & Constraints

This is an interactive problem. You are given an immutable linked list whose nodes expose printValue() and getNext(). Print all values in reverse order, one per line. Constraints: the number of nodes is in [1, 100].

💡 Core Algorithmic Approaches

  1. The list is immutable, so the reversal must come from the call order rather than from relinking.
  2. Recursion gives this for free: recurse to the end first, then print on the way back up.
  3. That is exactly a reverse traversal, with the recursion stack acting as the reversal buffer.
  4. An iterative alternative uses an explicit stack, which trades recursion depth for heap space.

💻 Benchmark Python3 Implementation

class Solution:
    def printLinkedListInReverse(self, head: "ImmutableListNode") -> None:
        if head is None:
            return
        self.printLinkedListInReverse(head.getNext())   # go to the end first
        head.printValue()                              # print on the way back


# Iterative variant with an explicit stack
class Solution2:
    def printLinkedListInReverse(self, head: "ImmutableListNode") -> None:
        stack = []
        cur = head
        while cur:
            stack.append(cur)
            cur = cur.getNext()
        while stack:
            stack.pop().printValue()

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each node is visited once.
💾 Space Complexity
O(n) for the recursion stack or the explicit stack.

⚠️ Interview Pitfalls & Follow-ups

  • Printing before recursing: that produces the original order, not the reverse.
  • Trying to reverse the list: the nodes are immutable, so relinking is impossible.
  • Assuming getNext() returns None at the end: it does, and the base case relies on it.
  • Deep recursion: with n up to 100 the default limit is fine, but the explicit stack is safer for larger inputs.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems