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