Print Linked List in Reverse

# Print Linked List in Reverse ## Difficulty Easy ## Tags `linked list`, `recursion`, `stack` ## Problem Statement Given a singly linked list, print its elements in reverse order without actually reversing the list structure. ## Constraints - Do not modify the list structure. - 0 ≤ list length ≤ 1000 - You can use recursion or an explicit stack. ## Signatures ### Python ```python def print_reverse(head: ListNode) -> List[int]: pass ``` ### Java ```java public class Solution { public List<Integer> print_reverse(ListNode head) { return null; } } ``` ### Csharp ```csharp public class Solution { public IList<int> print_reverse(ListNode head) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: vector<int> print_reverse(ListNode* head) { } }; ``` ### C ```c int* print_reverse(ListNode* head) { } ``` ### Ruby ```ruby def print_reverse(head) end ``` ### Perl ```perl sub print_reverse { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def print_reverse(head: ListNode): List[Int] = { } } ``` ### Haskell ```haskell print_reverse :: ... -> ... print_reverse args = undefined ``` ### Clojure ```clojure (defn print_reverse [head] ) ``` ### Scheme ```scheme (define (print_reverse head) ) ``` ## Examples ### Example 1 **Input:** ``` 1 → 2 → 3 → 4 → 5 ``` **Output:** ``` [5, 4, 3, 2, 1] ``` ### Example 2 **Input:** ``` 1 ``` **Output:** ``` [1] ``` ### Example 3 **Input:** ``` (empty list) ``` **Output:** ``` [] ``` ## Hints ### Recursive Approach 1. Recurse to the end of the list first. 2. Print/collect the value after the recursive call returns. 3. The call stack naturally reverses the order. ```python def print_reverse(head): result = [] def helper(node): if node is None: return helper(node.next) # Recurse first result.append(node.val) # Then collect helper(head) return result ``` ### Iterative Approach Use an explicit stack: push all values, then pop them.