1265. Print Immutable Linked List in Reverse - Explanation

Description

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.

Example 1:

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

Output: [4,3,2,1]

Example 2:

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

Output: [-5,3,-1,-4,0]

Example 3:

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?
Linear time complexity and less than linear space complexity?

1. Recursion

class Solution:
    def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None:
        if head is not None:
            self.printLinkedListInReverse(head.getNext())
            head.printValue()

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Where $n$ is the size of the linked list.

2. Using Stack

class Solution:
    def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None:
        stack = []
        while head:
            stack.append(head)
            head = head.getNext()

        while stack:
            node = stack.pop()
            node.printValue()

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Where $n$ is the size of the linked list.

3. Square Root Decomposition

class Solution:
    def printLinkedListInReverseRecursively(self, head: 'ImmutableListNode', size: int) -> None:
        if size > 0 and head is not None:
            self.printLinkedListInReverseRecursively(head.getNext(), size - 1)
            head.printValue()

    def getLinkedListSize(self, head: 'ImmutableListNode') -> int:
        size = 0
        while head is not None:
            size += 1
            head = head.getNext()
        return size

    def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None:
        linked_list_size = self.getLinkedListSize(head)
        block_size = math.ceil(math.sqrt(linked_list_size))

        blocks = []
        curr = head
        for i in range(linked_list_size):
            if i % block_size == 0:
                blocks.append(curr)
            curr = curr.getNext()

        while blocks:
            self.printLinkedListInReverseRecursively(blocks.pop(), block_size)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(\sqrt n)$

Where $n$ is the size of the linked list.

4. Divide and Conquer

class Solution:
    def helper(self, start: 'ImmutableListNode', end: 'ImmutableListNode') -> None:
        if start is None or start == end:
            return
        if start.getNext() == end:
            start.printValue()
            return

        slow = start
        fast = start

        while fast != end and fast.getNext() != end:
            slow = slow.getNext()
            fast = fast.getNext().getNext()

        self.helper(slow, end)
        self.helper(start, slow)

    def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None:
        self.helper(head, None)

Time & Space Complexity

Time complexity: $O(n \cdot \log n)$
Space complexity: $O(\log n)$

Where $n$ is the size of the linked list.

5. Constant Space

class Solution:
    def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None:
        end = None

        while head != end:
            curr = head
            while curr.getNext() != end:
                curr = curr.getNext()
            curr.printValue()
            end = curr

Time & Space Complexity

Time complexity: $O(n^2)$
Space complexity: $O(1)$

Where $n$ is the size of the linked list.