剑指offer 从尾到头打印链表

题目描述

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

思路1：反转链表，然后遍历输出。（缺点：改变了链表）

思路2：符合先进后出，后进先出（栈）的思想，即先遍历的链表元素后输出，可以用栈来保存先遍历到的元素。

思路3：递归做法，本质上也是栈结构。（如果链表太长，容易导致栈溢出。）

思路2：

 1 /**
 2 *  struct ListNode {
 3 *        int val;
 4 *        struct ListNode *next;
 5 *        ListNode(int x) :
 6 *              val(x), next(NULL) {
 7 *        }
 8 *  };
 9 */
10 class Solution {
11 public:
12     vector<int> printListFromTailToHead(ListNode* head) {
13         std::stack<ListNode*> st;
14         vector<int> v;
15         ListNode *temp = head;
16         while (temp != nullptr) {
17             st.push(temp);
18             temp = temp->next;
19         }
20         while (! st.empty()) {
21             int tmp = st.top()->val;
22             v.push_back(tmp);
23             st.pop();
24         }
25         return v;
26     } 
27 }；

思路3：

 1 /**
 2 *  struct ListNode {
 3 *        int val;
 4 *        struct ListNode *next;
 5 *        ListNode(int x) :
 6 *              val(x), next(NULL) {
 7 *        }
 8 *  };
 9 */
10 class Solution {
11 public:
12     vector<int> printListFromTailToHead(ListNode* head) {
13         vector<int> v;
14         traverse(head, v);
15         return v;
16     }
17 private:
18     void traverse(ListNode *head, vector<int> &v) {
19         if (head != nullptr) {
20             if (head->next != nullptr) {
21                 traverse(head->next, v);
22             }
23             v.push_back(head->val);
24         }
25     }
26 };