从尾到头打印链表（Python and C++解法）

题目：

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

思路：

　　假设源链表节点为A->B->C->D->E,那么：

将A插到0位置：A->B->C->D->E；　　将B插到0位置：B->A->C->D->E；　　将C插到0位置：C->B->A->D->E；　　

将D插到0位置：D->C->B->A->E；　　将E插到0位置：E->D->C->B->A；

1 class Solution:
2     def printListFromTailToHead(self, listNode):
3         res = []  # 存储倒置后的结果
4         temp = listNode  # 链表头部
5         while temp:  # 链表当前节点不为None时
6             res.insert(0, temp.val)
7             temp = temp.next
8         return res

上述做法会改变链表的结构，不是一种高级做法。

　　链表的遍历顺序是从前到后，而打印顺序是从后到前，即先遍历的后打印，后遍历的先打印，这是一种栈的思维，于是可用栈实现打印顺序。

　　另外，递归的操作过程其实就是栈的顺序，因此也可以用递归实现打印顺序。

Python解法一：

 1 class Solution: 
 2     def printListFromTailToHead(self, listNode):
 3         if listNode == None:  # 判断头结点是否为空
 4             return []
 5         pNode = listNode  # 哨兵节点
 6         stack = []  # 栈
 7         while pNode != None:  # 入栈
 8             stack.append(pNode.val)  
 9             pNode = pNode.next
10         ArrayList = []
11         while len(stack) != 0:
12             ArrayList.append(stack.pop(-1))
13         return ArrayList

Python解法二：

 1 class Solution:
 2     def printListFromTailToHead(self, listNode):
 3         res = []
 4         def printListnode(listNode):
 5             if listNode:
 6                 printListnode(listNode.next)  # 先递归到最后一层
 7                 res.append(listNode.val)  # 添加值，退出函数，返回到上一层函数中的这行重复执行
 8                 
 9         printListnode(listNode)
10         return res

C++解法一：

 1 struct ListNode {
 2      int val;
 3      ListNode *next;
 4      ListNode(int x) : val(x), next(NULL) {}
 5  };
 6  
 7 class Solution {
 8 public:
 9     vector<int> reversePrint(ListNode* head) {
10         if (head == NULL)
11             return {};
12         ListNode *pNode = head;  // 哨兵节点
13         stack<int> aStack;
14         while (pNode != NULL) {
15             aStack.push(pNode->val);
16             pNode = pNode->next;
17         }
18         vector<int> res;
19         while (aStack.size() != 0) {
20             res.push_back(aStack.top());
21             aStack.pop();
22         }
23         return res;
24     }
25 };

C++解法二：

 1  struct ListNode {
 2      int val;
 3      ListNode *next;
 4      ListNode(int x) : val(x), next(NULL) {}
 5  };
 6  
 7  class Solution {
 8  public:
 9      vector<int> res;  //  应置为全局变量
10      vector<int> reversePrint(ListNode* head) {
11          if (head != NULL) {
12              ListNode *pNode = head;  // 哨兵节点
13              if (pNode != NULL) {
14                  reversePrint(pNode->next);  // 递归到最后一层
15                  res.push_back(pNode->val);
16              }
17          }
18          return res;
19      }
20  };