# Question

Formatted question description: https://leetcode.ca/all/1265.html

 1265. Print Immutable Linked List in Reverse

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.

Example 1:

Output: [4,3,2,1]
Example 2:

Output: [-5,3,-1,-4,0]
Example 3:

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

Could you solve this problem in:

Constant space complexity?
Linear time complexity and less than linear space complexity?



# Algorithm

Similar to 206 Reverse Linked List

DFS, recursion before print current node.

• space is O(N), since need to store previous recursion

Could you solve this problem in:

Constant space complexity? Linear time complexity and less than linear space complexity?

# Code

Java

• 

/*
Algorithms:

1) Find n = count nodes in linked list.
2) For i = n to 1, do following.
Print i-th node using get n-th node function

*/
public class Solution_followup {
return;
}

// Count nodes

// print one by one
for (int i = n; i >= 1; i--) {
}

}

/* Counts no. of nodes in linked list */
int count = 0; // Initialize count
ImmutableListNode current = head; // Initialize current
while (current != null) {
count++;
current = current.getNext();
}
return count;
}

/* Takes head pointer of the linked list and index as arguments and return data at index*/
private void printNth(ImmutableListNode head, int n) {
for (int i = 0; i < n - 1 && curr != null; i++) {
curr = curr.getNext();
}

curr.printValue();
}

}

public class Solution {
return;
}

// recursion before print current node

}
}

interface ImmutableListNode {
void printValue(); // print the value of this node.

ImmutableListNode getNext(); // return the next node.
}
}


• // OJ: https://leetcode.com/problems/print-immutable-linked-list-in-reverse/
// Time: O(N)
// Space: O(N)
class Solution {
public:
}
};

• class Solution(object):
def generateSentences(self, synonyms, text):
"""
:type synonyms: List[List[str]]
:type text: str
:rtype: List[str]
"""
text = '#' + text.replace(' ', '#') + '#'
queue = [text]
for (w1,w2) in synonyms:
for text in queue :
newtext = text.replace('#' + w1+'#','#' + w2+'#',1)
if newtext != text and newtext not in queue:
queue.append(newtext)
newtext = text.replace('#' + w2 + '#', '#' + w1 + '#',1)
if newtext != text and newtext not in queue:
queue.append(newtext)
res = []
for i in sorted(queue):
newtext = i.replace('#', ' ')
res.append(newtext[1:-1])
return res