从尾到头打印链表

规则
输入：链表head
输出: 字符串，每个元素的值
case：

head为null
只有一个节点
有多个节点

思路

从头到尾打印比较简单，但从尾到头打印就需要进行一些思考了 ，首先要思考能否修改链表，比如讲链表进行逆序再打印，复杂度为O(n)和O(1)。本题目的要求不能修改链表。
思路1：申请空间，构造另外一个链表，使用头插法，复杂度为O(n)和O(n)
思路2：遍历链表，保存到栈中，最后出栈并打印，复杂度为O(n)和O(n)
思路3：有了栈的思路，可以使用递归，复杂度为O(n)和O(n)

代码

// 使用栈
public String reverse(ListNode head) {
		if(head == null) return "";
		Stack<Integer> stack = new Stack<Integer>();
		while(head != null) {
			stack.push(head.val);
			head = head.next;
		}
		StringBuilder sb = new StringBuilder();
		while(!stack.isEmpty()) {
			int tmp = stack.pop();
			sb.append(tmp);
		}
		return sb.toString();
	}
// 递归    
public String reverse(ListNode head) {
		if(head == null) return "";
		 return reverse(head.next) + head.val;
	}