题目难度：简单

题目描述：
输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。
如输入{1,2,3}的链表如下图:

返回一个数组为[3,2,1]
0 <= 链表长度 <= 10000
示例1
```
输入：{67,0,24,58}
返回值：[58,24,0,67]
```

思路一：用数组先存下来，再打印（反转数组）

时间复杂度：O(n); 空间复杂度：O(n)
写法一：
提交结果：答案正确运行时间：6ms 占用内存：1036KB

class Solution {
public:
  vector<int> printListFromTailToHead(ListNode* head) {
      vector<int> temp, res;

      while (head) {
          temp.push_back(head->val);
          head = head->next;
      }

      int len = temp.size();
      for (int i = len - 1; i >= 0; i--) {
          res.push_back(temp[i]);
      }

      return res;
  }
}

写法二：
提交结果：答案正确运行时间：6ms 占用内存：896KB

vector<int> printListFromTailToHead(ListNode* head) {
  vector<int> res;

  while (head) {
      res.push_back(head->val);
      head= head->next;
  }

  // 可优化
  int len = res.size();
  if (len % 2 == 0) {
      for (int i = 0, j = len - 1; i <= j; i++, j--) {
          swap(res[i], res[j]);
      }
  } else {
      int mid = (len - 1) >> 1;
      for (int i = mid - 1, j = mid + 1; i >= 0 || j < len; i--, j++) {
          swap(res[i], res[j]);
      }
  }
  return res;
}

写法三：（推荐）使用栈结构-先进后出
提交结果：答案正确运行时间：6ms 占用内存：896KB

vector<int> printListFromTailToHead(ListNode* head) {
  stack<int> stk;
  vector<int> res;

  while (head) {
      stk.push(head->val);
      head = head->next;
  }

  while (!stk.empty()) {
      res.push_back(stk.top());
      stk.pop();
  }

  return res;
}

思路二：反转链表

时间复杂度：O(n)；空间复杂度：O(n)

class Solution {
  vector<int> printListFromTailToHead(ListNode* head) {
      vector<int> res;
      ListNode* cur = head->next, pre = nullptr;

      while (head) {
          head->next = pre;
          pre = head;
          head = cur;
          cur = head->next; 
      }
      head = pre;
      while(head) {
          res.push_back(head->val);
          head = head->next;
      }
      return res;
  }
}

JZ6 从尾到头打印链表

题目难度：简单

题目描述：

示例1

思路一：用数组先存下来，再打印（反转数组）

思路二：反转链表

😘😘😘😘😘😘😘😘😘😘😘

😘😘😘😘😘😘😘😘😘😘

😘😘😘😘😘😘😘😘😘

😘😘😘😘😘😘😘😘

😘😘😘😘😘😘😘

😘😘😘😘😘😘