Print Immutable Linked List in Reverse - Practice Coding Problems

Print Immutable Linked List in Reverse - 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.

Input & Output

Example 1 — Basic List

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

› Output: 4 3 2 1

💡 Note: Print each value in reverse order: start with 4 (last node), then 3, 2, and finally 1 (first node)

Example 2 — Single Node

$ Input: head = [1]

› Output: 1

💡 Note: Only one node, so print its value: 1

Example 3 — Two Nodes

$ Input: head = [1,2]

› Output: 2 1

💡 Note: Print in reverse: 2 (second node) then 1 (first node)

Constraints

1 ≤ Number of nodes ≤ 1000
0 ≤ Node.val ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Immutable linked list: 1→2→3→4

Process

Use recursion or stack to reverse printing order

Output

Print values: 4, 3, 2, 1

Key Takeaway

🎯 Key Insight: Recursion's call stack naturally provides the reverse order we need

Asked in

G Google 35 f Facebook 28 a Amazon 22 M Microsoft 18

The key insight is to use recursion's natural property of unwinding in reverse order. The optimal recursive approach makes calls forward to the end, then prints values as the call stack unwinds. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Stack-Based Solution	O(n)	O(n)	Traverse once to push all values onto stack, then pop to print in reverse
Recursive Solution	O(n)	O(n)	Use recursion to naturally reverse order - print after recursive calls return
Multiple Pass Solution	O(n²)	O(1)	Count nodes, then traverse n times to print nth node from end

Stack-Based Solution — Algorithm Steps

Step 1: Traverse the list once, pushing each value onto a stack
Step 2: Pop values from stack and print them (LIFO gives reverse order)

Visualization

Tap to expand

Step-by-Step Walkthrough

Push Phase

Traverse forward pushing each value onto stack

Pop Phase

Pop values from stack (LIFO order gives reverse)

Result

Values printed in reverse: 4, 3, 2, 1

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct ImmutableListNode {
    int val;
    struct ImmutableListNode* next;
} ImmutableListNode;

void printValue(ImmutableListNode* node) {
    printf("%d\n", node->val);
}

ImmutableListNode* getNext(ImmutableListNode* node) {
    return node->next;
}

void solution(ImmutableListNode* head) {
    if (!head) return;
    
    // Push all values onto stack (using array)
    int stack[1000];
    int top = -1;
    
    ImmutableListNode* current = head;
    while (current) {
        stack[++top] = current->val;
        current = getNext(current);
    }
    
    // Pop and print in reverse order
    while (top >= 0) {
        printf("%d\n", stack[top--]);
    }
}

ImmutableListNode* buildList(int* values, int size) {
    if (size == 0) return NULL;
    ImmutableListNode* head = (ImmutableListNode*)malloc(sizeof(ImmutableListNode));
    head->val = values[0];
    head->next = NULL;
    
    ImmutableListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = (ImmutableListNode*)malloc(sizeof(ImmutableListNode));
        current = current->next;
        current->val = values[i];
        current->next = NULL;
    }
    return head;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int values[1000];
    int count = 0;
    
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int num = atoi(token);
        if (num != 0 || strcmp(token, "0") == 0) {
            values[count++] = num;
        }
        token = strtok(NULL, "[,]");
    }
    
    ImmutableListNode* head = buildList(values, count);
    solution(head);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single traversal to push all values, then O(n) to pop and print

✓ Linear Growth

Space Complexity

O(n)

Stack stores all n node values

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

843 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Stack-Based Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler