1265. Print Immutable Linked List in Reverse Solution

//O(n) Space, O(n) Time
class Solution {
    public void printLinkedListInReverse(ImmutableListNode head) {
        List<ImmutableListNode> temp = new ArrayList<>();
        while (head != null) {
            temp.add(head);
            head = head.getNext();
        }
        for (int i = temp.size() - 1; i >= 0; i--) temp.get(i).printValue();
    }
}


//O(1) Space, O(n ^ 2) Time
class Solution {
    public void printLinkedListInReverse(ImmutableListNode head) {
        ImmutableListNode next = null;
        while (next != head) {
            ImmutableListNode cur = head;
            while (cur.getNext() != next) cur = cur.getNext();
            cur.printValue();
            next = cur;
        }
    }
}


//O(sqrt(n)) Space, O(n) Time
class Solution {
    public void printLinkedListInReverse(ImmutableListNode head) {
        int n = 0;
        ImmutableListNode p = head;
        while (p != null) {
            n++;
            p = p.getNext();
        }

        int len = (int)Math.sqrt(n);
        List<ImmutableListNode> start = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (i % len == 0) start.add(head);
            head = head.getNext();
        }

        start.add(null);
        for (int i = start.size() - 2; i >= 0; i--) {
            print(start.get(i), start.get(i + 1));
        }
    }

    private void print(ImmutableListNode head, ImmutableListNode end) {
        List<ImmutableListNode> temp = new ArrayList<>();
        while (head != end) {
            temp.add(head);
            head = head.getNext();
        }
        for (int i = temp.size() - 1; i >= 0; i--) {
            temp.get(i).printValue();
        }
    }
}