Problem statement

https://leetcode.com/problems/print-immutable-linked-list-in-reverse/

Solution

The idea is to use recursion dfs(node, n), where node is node we want to start and n is number of nodes we want to deal with. For this we can traverse the second half first, then the first one.

Complexity

We have recursion F(n) = 2*F(n/2) + O(n), which will lead to O(n log n) time complexity. Space complexity is O(log n) due to recursion stack.

Remark

There is also O(n) time and O(sqrt(n)) space solution, using sqrt decomposition idea: we split everything in sqrt(n) blocks of size sqrt(n) and save starts of blocks in some list. For each block we can print it in `sqrt(n) time and space, using recursion.

In fact this idea can be extended to use double level decompositions and so on.

Code

class Solution:
    def printLinkedListInReverse(self, head):
        node, n = head, 0
        while node:
            node = node.getNext()
            n += 1
            
        def dfs(node, n):
            if n == 1: 
                node.printValue()
                return
            mid = node
            for _ in range(n//2): mid = mid.getNext()
            dfs(mid, n-n//2)
            dfs(node, n//2)
            
        dfs(head, n)