Print Immutable Linked List in Reverse

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.

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.

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.