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.

Examples

Example 1:

1
2

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

Example 2:

1
2

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

Example 3:

1
2

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?

Solution

Method 1 - Recursion (Call Stack)

Intuition

The problem restricts us to only use the provided ImmutableListNode interface, which allows us to print the value and get the next node, but not to modify the list or access its value directly. To print the list in reverse, we can use recursion (which uses the call stack) or an explicit stack. For the follow-up, a block-reversal approach can achieve O(1) space, but recursion is the most straightforward.

Approach

We traverse the list recursively to the end starting from head, then print the value on the way back. This prints the values in reverse order. This uses O(n) space due to the call stack. For O(1) space, we can use a block-reversal technique, but it’s more complex and rarely required in interviews.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// The ImmutableListNode interface is provided by the problem:
// class ImmutableListNode {
//  public:
//   void printValue() const; // print the value of this node.
//   ImmutableListNode* getNext() const; // return the next node.
// };

void printLinkedListInReverse(const ImmutableListNode* head) {
    if (!head) return;
    printLinkedListInReverse(head->getNext());
    head->printValue();
}

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// type ImmutableListNode interface {
//     PrintValue()
//     GetNext() ImmutableListNode
// }
func printLinkedListInReverse(head ImmutableListNode) {
    if head == nil {
        return
    }
    printLinkedListInReverse(head.GetNext())
    head.PrintValue()
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// This is the ImmutableListNode's API interface.
// You should not implement it, or speculate about its implementation
// interface ImmutableListNode {
//     public void printValue(); // print the value of this node.
//     public ImmutableListNode getNext(); // return the next node.
// }
class Solution {
    public void printLinkedListInReverse(ImmutableListNode head) {
        if (head == null) return;
        printLinkedListInReverse(head.getNext());
        head.printValue();
    }
}
1
2
3
4
5
6
7
8
9

// interface ImmutableListNode {
//     fun printValue()
//     fun getNext(): ImmutableListNode?
// }
fun printLinkedListInReverse(head: ImmutableListNode?) {
    if (head == null) return
    printLinkedListInReverse(head.getNext())
    head.printValue()
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# """
# class ImmutableListNode:
#     def printValue(self) -> None: ...
#     def getNext(self) -> 'ImmutableListNode': ...
# """
def printLinkedListInReverse(head: 'ImmutableListNode') -> None:
    if head is None:
        return
    printLinkedListInReverse(head.getNext())
    head.printValue()

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// trait ImmutableListNode {
//     fn print_value(&self);
//     fn get_next(&self) -> Option<&dyn ImmutableListNode>;
// }
fn print_linked_list_in_reverse(head: Option<&dyn ImmutableListNode>) {
    if let Some(node) = head {
        print_linked_list_in_reverse(node.get_next());
        node.print_value();
    }
}
1
2
3
4
5
6
7
8
9

// interface ImmutableListNode {
//   printValue(): void;
//   getNext(): ImmutableListNode | null;
// }
function printLinkedListInReverse(head: ImmutableListNode | null): void {
    if (!head) return;
    printLinkedListInReverse(head.getNext());
    head.printValue();
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the list.
  • 🧺 Space complexity: O(n) due to recursion stack. For O(1) space, a block-reversal approach is required (advanced, not shown here).