Meta Interview Question — LeetCode 1265

In this post, we are going to discuss leetcode 1265 — Print Immutable Linked List in Reverse, which is asked in Meta interviews.

Problem Analysis

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]

My Thinking Process

For this question, we need to print the last nodes before printing the current node.

This is a typical post-order DFS problem. I.e., to traverse the children nodes first, then process the current node.

Code Implementation

Base on the analysis above, below is my implementation of the problem.