给您一个不可变的链表，使用下列接口逆序打印每个节点的值：
- ImmutableListNode: 描述不可变链表的接口，链表的头节点已给出。
您需要使用以下函数来访问此链表（您 不能 直接访问 ImmutableListNode）：
- ImmutableListNode.printValue()：打印当前节点的值。
- ImmutableListNode.getNext()：返回下一个节点。
输入只用来内部初始化链表。您不可以通过修改链表解决问题。也就是说，您只能通过上述 API 来操作链表。
示例 1：
输入：head = [1,2,3,4] 输出：[4,3,2,1]解法一：栈 思路
利用栈后进先出特性，逆序打印
复杂度时间复杂度： O ( N ) O(N) O(N)
空间复杂度： O ( N ) O(N) O(N)
代码class Solution {
public void printlinkedListInReverse(ImmutableListNode head) {
Stack s = new Stack<>();
for (ImmutableListNode p = head; p != null; p = p.getNext()) {
s.push(p);
}
while (!s.isEmpty()) {
s.pop().printValue();
}
}
}
解法二：递归
思路
不用自己开辟栈，用系统栈，就是递归
复杂度时间复杂度： O ( N ) O(N) O(N)
空间复杂度： O ( N ) O(N) O(N)，虽然没自己开辟栈，但用到了系统栈
代码class Solution {
public void printlinkedListInReverse(ImmutableListNode head) {
if (head == null) return;
printlinkedListInReverse(head.getNext());
head.printValue();
}
}
总结
凡事用栈解决的均能用递归，凡事用递归解决的均能用栈。
取舍在于是要安全还是要速度。
