> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Print Immutable Linked List in Reverse

> Tested Python solution for LeetCode 1265 with 14 pytest cases. Generate a practice environment with lcpy.

LeetCode 1265, [Medium](/catalog/medium). Topics: [Stack](/catalog/topics/stack), [Recursion](/catalog/topics/recursion), [Linked List](/catalog/topics/linked-list), [Two Pointers](/catalog/topics/two-pointers). [View on LeetCode](https://leetcode.com/problems/print-immutable-linked-list-in-reverse/description/).

Generate this problem as a practice environment: tested reference solution, 14 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1265   # by problem number
lcpy gen -s print_immutable_linked_list_in_reverse   # by problem name
```

## Problem

You are given an immutable linked list, print out all values of each node in reverse with the help of the following interface:

* `ImmutableListNode`: An interface of immutable linked list, you are given the head of the list.

You need to use the following functions to access the linked list (you **can't** access the `ImmutableListNode` directly):

* `ImmutableListNode.printValue()`: Print value of the current node.
* `ImmutableListNode.getNext()`: Return the next node.

The input is only given to initialize the linked list internally. You must solve this problem without modifying the linked list. In other words, you must operate the linked list using only the mentioned APIs.

The Python harness models the judge: each `print_value()` call records the node value, and the recorded values are compared with the expected reversed sequence.

### Examples

```
Input: head = [1,2,3,4]
Output: [4,3,2,1]
```

```
Input: head = [0,-4,-1,3,-5]
Output: [-5,3,-1,-4,0]
```

```
Input: head = [-2,0,6,4,4,-6]
Output: [-6,4,4,6,0,-2]
```

### Constraints

* The length of the linked list is between `[1, 1000]`.
* The value of each node in the linked list is between `[-1000, 1000]`.

**Follow up:**

* Could you solve this problem in constant space complexity?
* Could you solve this problem in linear time complexity and less than linear space complexity?

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/print_immutable_linked_list_in_reverse/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/print_immutable_linked_list_in_reverse/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from __future__ import annotations

import math
from typing import ClassVar


class ImmutableListNode:
    # Test-harness API: immutable list node; print_value records the value
    printed: ClassVar[list[int]] = []

    def __init__(self, value: int, next_node: ImmutableListNode | None = None) -> None:
        self.value = value
        self.next_node = next_node

    def get_next(self) -> ImmutableListNode | None:
        return self.next_node

    def print_value(self) -> None:
        ImmutableListNode.printed.append(self.value)


class Solution:
    # Time: O(n) - one pass to slice blocks, one pass to print
    # Space: O(sqrt(n)) - one stored head per block plus per-block recursion depth
    def print_linked_list_in_reverse(self, head: ImmutableListNode) -> None:
        size = self._count(head)
        block_size = max(1, math.isqrt(size))
        heads = self._block_heads(head, block_size)
        for start in reversed(heads):
            self._print_block(start, block_size)

    def _count(self, node: ImmutableListNode | None) -> int:
        total = 0
        while node is not None:
            total += 1
            node = node.get_next()
        return total

    def _block_heads(self, head: ImmutableListNode, block_size: int) -> list[ImmutableListNode]:
        heads: list[ImmutableListNode] = []
        node: ImmutableListNode | None = head
        while node is not None:
            heads.append(node)
            for _ in range(block_size):
                nxt = node.get_next()
                if nxt is None:
                    return heads
                node = nxt
        return heads

    def _print_block(self, node: ImmutableListNode | None, remaining: int) -> None:
        if node is None or remaining == 0:
            return
        self._print_block(node.get_next(), remaining - 1)
        node.print_value()
```

## Complexity

| Time | Space |
| - | - |
| O(n) - one pass to slice blocks, one pass to print | O(sqrt(n)) - one stored head per block plus per-block recursion depth |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.