从尾到头打印链表（Python and C++解法）
2021-05-06 19:27
标签：style 思维 tor code pen python and 假设 app 输入一个链表的头结点，按链表从尾到头的顺序返回一个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； 上述做法会改变链表的结构，不是一种高级做法。 链表的遍历顺序是从前到后，而打印顺序是从后到前，即先遍历的后打印，后遍历的先打印，这是一种栈的思维，于是可用栈实现打印顺序。 另外，递归的操作过程其实就是栈的顺序，因此也可以用递归实现打印顺序。 从尾到头打印链表（Python and C++解法） 标签：style 思维 tor code pen python and 假设 app 原文地址：https://www.cnblogs.com/kongzimengzixiaozhuzi/p/13179223.html题目：
思路：
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 vectorint> reversePrint(ListNode* head) {
10 if (head == NULL)
11 return {};
12 ListNode *pNode = head; // 哨兵节点
13 stackint> aStack;
14 while (pNode != NULL) {
15 aStack.push(pNode->val);
16 pNode = pNode->next;
17 }
18 vectorint> 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 vectorint> res; // 应置为全局变量
10 vectorint> 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 };
上一篇：SpringMVC简单案例
下一篇：Python实现AI换脸功能