Skip to content

1265. Print Immutable Linked List in Reverse 👍

Approach 1: Recursive

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
/**
 * // This is the ImmutableListNode's API interface.
 * // You should not implement it, or speculate about its implementation.
 * class ImmutableListNode {
 *  public:
 *   void printValue(); // Print the value of the node.
 *   ImmutableListNode* getNext(); // Returns the next node.
 * };
 */

class Solution {
 public:
  void printLinkedListInReverse(ImmutableListNode* head) {
    if (head == nullptr)
      return;

    printLinkedListInReverse(head->getNext());
    head->printValue();
  }
};

Approach 2: Stack

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * // This is the ImmutableListNode's API interface.
 * // You should not implement it, or speculate about its implementation.
 * class ImmutableListNode {
 *  public:
 *   void printValue(); // Print the value of the node.
 *   ImmutableListNode* getNext(); // Returns the next node.
 * };
 */

class Solution {
 public:
  void printLinkedListInReverse(ImmutableListNode* head) {
    stack<ImmutableListNode*> stack;

    while (head != nullptr) {
      stack.push(head);
      head = head->getNext();
    }

    while (!stack.empty())
      stack.top()->printValue(), stack.pop();
  }
};