從尾到頭打印鏈表
**規則**
輸入:鏈表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;
}
```