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
- The list is immutable, so the reversal must come from the call order rather than from relinking.
- Recursion gives this for free: recurse to the end first, then print on the way back up.
- That is exactly a reverse traversal, with the recursion stack acting as the reversal buffer.
- 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()returnsNoneat 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.