Leetcode 1265. Print Immutable Linked List in Reverse

Problem Explanation:

The given problem asks us to print out all values of each node in a linked list in reverse order. A key condition is that the linked list is immutable, which means that we cannot modify its structure or its nodes. We are provided access to the linked list through two APIs: ImmutableListNode.printValue() for printing the value of a node, and ImmutableListNode.getNext() for accessing the next node of a linked list.

One additional challenge includes finding a solution to this problem with constant space complexity or linear time complexity with less than linear space complexity.

Let's illustrate this with an example:

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

Here, we want to print the values of the linked list which starts with a node having a value of 1, followed by nodes with values 2, 3, and 4, but in reverse order, i.e., 4, 3, 2, 1.

Solution Approach:

The problem can be solved efficiently using recursion, a method where the function calls itself, in this case- until the end of the linked list is reached. We start from the head of the linked list, and for each node, we recursively call the function for its next node before printing its value. This ensures that the print commands for the subsequent nodes are executed before the current node, hence achieving the reverse printing result.

For example, if our linked list is [1,2,3,4], we start from the head having value 1, call the function recursively for the next node having value 2, and so on. By the time we reach the end of the linked list having value 4, we have set up recursive calls that will execute in the reverse order- printing 4 first, then 3, then 2, and finally 1.

Python Solution:

1
2python
3# Definition for ImmutableListNode
4class ImmutableListNode:
5  def printValue(self):
6    ...
7   
8  def getNext(self):
9    ...
10
11class Solution:
12  def printLinkedListInReverse(self, head):
13    if head is not None:
14      self.printLinkedListInReverse(head.getNext())
15      head.printValue()

The Python solution follows the explained recursive approach. In the printLinkedListInReverse() function it checks if head is not None. If it is None, it means we have reached the end of the linked list. If not, it continues to call itself recursively for the next node and then prints the current node value.

Java Solution:

1
2java
3interface ImmutableListNode {
4  void printValue(); // Print the value of this node.
5  ImmutableListNode getNext(); // Return the next node.
6};
7
8class Solution {
9  public void printLinkedListInReverse(ImmutableListNode head) {
10    if (head != null) {
11      printLinkedListInReverse(head.getNext());
12      head.printValue();
13    }
14  }
15}

The Java solution works similar to Python solution using recursion.

JavaScript Solution:

1
2javascript
3// definition for ImmutableListNode
4class ImmutableListNode {
5  printValue() {
6    ...
7  }
8  getNext() {
9    ...
10  }
11}
12
13class Solution {
14  printLinkedListInReverse(head) {
15    if (head !== null) {
16      this.printLinkedListInReverse(head.getNext());
17      head.printValue();
18    }
19  }
20}

JavaScript solution also follow same recursive approach.

C++ Solution:

1
2cpp
3// This is the ImmutableListNode's API interface.
4// You should not implement it, or speculate about its implementation
5class ImmutableListNode {
6 public:
7  void printValue(); // Print the value of this node.
8  ImmutableListNode* getNext(); // Return the next node.
9};
10
11class Solution {
12 public:
13  void printLinkedListInReverse(ImmutableListNode* head) {
14    if (head) {
15      printLinkedListInReverse(head->getNext());
16      head->printValue();
17    }
18  }
19};

The C++ solution is practically the same as the Python, Java, and JavaScript solutions.

C# Solution:

1
2csharp
3public interface ImmutableListNode {
4  void printValue(); // Print the value of the node.
5  ImmutableListNode getNext(); // Returns the next node.
6}
7
8public class Solution {
9  public void printLinkedListInReverse(ImmutableListNode head) {
10    if (head != null) {
11      printLinkedListInReverse(head.getNext());
12      head.printValue();
13    }
14  }
15}

The C# solution, like the other language solutions, uses recursion to achieve headline requirements.## Conclusion:

In concluding, the problem requires us to print values of nodes in a linked list in a reversed order. This problem can be efficiently solved by using recursion, which allows us to reach the end (tail) of the list first and then to print the node's values while unwinding the call stack.

The solution presents the code-blocks for various programming languages such as Python, Java Script, Java, C++ and C#. In each solution, a recursive function printLinkedListInReverse is used which takes an ImmutableListNode as a parameter, checks if the node is not null, then recursively calls itself with the next node's reference and finally print the current node's value.

Keep in mind that recursive methods have an overhead as they could lead to a stack overflow for larger inputs due to excessive recursive calls, which should be considered when handling large data and linked lists.

An alternative solution could be to use an iterative approach with an auxiliary data structure like a stack, where you can store the nodes or their values while traversing the given linked list in order and then pop the elements out of stack to print in reversed order. However, this has a higher space complexity due to the use of the additional data structure. This is why the recursive solution is optimal in terms of both space and time complexity for this problem.