Vultr DocsLatest Content

Print Immutable Linked List in Reverse

Updated on 10 July, 2025
Print Immutable Linked List in Reverse header image

Problem Statement

In this problem, you are provided with an immutable linked list, and you must print the values of each node in the reverse order. The linked list is accessed through the ImmutableListNode interface, which provides two specific functions:

  • ImmutableListNode.printValue(): This method allows you to print the value of the node it is called upon.
  • ImmutableListNode.getNext(): This method returns the next node in the list.

Since the linked list is immutable, you cannot modify it. The challenge is to make use of the given interface methods to retrieve and print all node values in reverse without altering the structure or content of the linked list. The input, which is used to simulate the instantiation of the linked list internally, is abstracted from you, meaning you'll deal with the linked list solely through the provided methods.

Examples

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].

Approach and Intuition

The problem at hand asks us to print the values of a linked list in reverse, utilizing only the given interface methods. This requires a strategic approach since the linked list is immutable and can only be navigated linearly from head to tail. Here's a succinct strategy to achieve our objective:

  1. A recursive approach can be effective, as it leverages the call stack to reverse the process flow, which suits our need to reverse the output. By following this strategy:

    • Iterate through the list using the getNext() method until you reach the last node.
    • On reaching the last node or the base case (no more nodes), begin the unwinding phase of the recursion.
    • During the unwinding phase, utilize the printValue() method. This will print the nodes' values from last to first, effectively reversing the order.

  2. Alternatively, for environments where recursion depth could be a concern (with linked lists approaching the upper constraint of 1000 nodes), an iterative approach with an auxiliary data structure might be necessary:

    • Iterate through the linked list from head to tail, pushing each node's value onto a stack (last-in, first-out behavior).
    • Once all values are on the stack, pop them off one by one and print. This will print the values in reverse order as required.

The constraints confirm that the recursive depth would typically be manageable within the system stack, but for maximum robustness in extreme cases, both approaches could be considered. In practice, the choice might depend on system-specific limitations regarding recursion depth or the overhead of auxiliary data structures.

Solutions

  • C++
cpp 
class Solution {
public:
    void reversePrintLinkedList(ImmutableListNode* start) {
        ImmutableListNode* node;
        ImmutableListNode* last = NULL;
    
        while (start != last) {
            node = start;
            while (node->getNext() != last) {
                node = node->getNext();
            }
            node->printValue();
            last = node;
        }
    }
};

The provided C++ solution defines a method reversePrintLinkedList to print the values of an immutable linked list in reverse. This method takes a single parameter, start, which is a pointer to the first node of the linked list of type ImmutableListNode.

  • The algorithm initializes two pointers, node and last, where last is set to NULL initially. This pointer helps to identify the end of the list during the traversal.

  • The outer while loop continues until the start pointer equals last, indicating that all nodes have been processed in reverse order.

  • Inside the outer loop, the node pointer is reset to the start of the list for each iteration. A nested while loop then advances the node pointer to the next node until it reaches the last processed node.

  • Once the last node of the current reversed portion is found, its value is printed using node->printValue().

  • After printing, last is updated to the current node, effectively reducing the list size for the next iteration.

The code efficiently reverses the traversal of an immutable linked list without modifying the list itself, relying on pointer manipulation to track and print each node in reverse order.

  • Java
java 
class Solution {
    public void reversePrintLinkedList(ImmutableListNode startNode) {
        ImmutableListNode position;
        ImmutableListNode lastNode = null;
    
        while (startNode != lastNode) {
            position = startNode;
            while (position.getNext() != lastNode) {
                position = position.getNext();
            }
            position.printValue();
            lastNode = position;
        }
    }
}

The provided Java program defines a method to reverse print an immutable linked list. The method named reversePrintLinkedList accepts a starting node of the list.

Here's a breakdown of the method's approach:

  • Define two variables, position and lastNode, initially set lastNode to null.
  • Utilize a while loop to iterate until startNode is not equal to lastNode.
  • Within this loop, use another nested while loop to traverse from startNode to the node just before lastNode. This helps in identifying the last unprinted node.
  • Print the value of the node that was identified as the last unprinted node.
  • Update lastNode to this currently printed node to ensure that the next iteration prints the previous node.

This approach effectively reverses the order of printing the linked list without modifying the list itself, adhering to its immutability constraint.

  • Python
python 
class Solution:
    def reversePrint(self, start: 'ImmutableListNode') -> None:
        last_node = None
    
        while start != last_node:
            current = start
            while current.getNext() != last_node:
                current = current.getNext()
            current.printValue()
            last_node = current

In the provided Python program, the goal is to print the elements of an immutable linked list in reverse order. The reversePrint method accomplishes this without modifying the list:

  • Initially, last_node is set to None, which helps in identifying when the reversal process has covered all nodes in the list.
  • A while loop runs as long as the start node (the head of the list) isn't equal to last_node.
  • Inside the outer while loop, the current variable is initialized to the start node. A inner while loop then navigates through the list using current.getNext(), iterating until current.getNext() equals last_node.
  • After reaching the end of the portion of the list not yet printed in reverse, current.printValue() prints the value of the current node.
  • Update last_node to current to gradually decrease the part of the list being considered in each iteration.

This strategy iteratively prints all nodes from last to first by progressively considering smaller sections of the list, without any need to actually reverse the nodes or modify the list structure.

Comments

No comments yet.