本题来自《剑指offer》 从尾到头打印链表
题目：
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
思路：
方案一：首先遍历到尾部，然后从尾部进行到头值进行操作，后进先出，符合栈的规则。采用栈进行存储数据。采用C++编程。
方案二：采用递归的方式，其实栈就是递归的思路。采用C++编程。
方案三：遍历期间直接将值存储，最后翻转数据即可。采用python编程。
C++ Code （栈方式）：
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
std::vector<int> result; //存放结果值
std::stack<ListNode*> nodes; //栈，存放其节点的值
ListNode* phead = head;
int val;
while (phead != NULL){ //遍历链表
nodes.push(phead); //将节点加入到栈中
phead = phead->next;
}
while (!nodes.empty()){ //从栈中取数据
val = nodes.top()->val;
result.push_back(val);
nodes.pop();
}
return result;
}
};
C++ Code （递归方式）：
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
std::vector<int> result; //用来存放结果值
result = ListFromTailToHead(result,head);
return result;
}
vector<int> ListFromTailToHead(vector<int> result,ListNode* head){
if (head != NULL){ //条件为节点不为空
result = ListFromTailToHead(result,head->next); //递归调用
result.push_back(head->val); //递归结束返回，返回其值
}
return result;
}
};
Python Code：
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None class Solution:
# 返回从尾部到头部的列表值序列，例如[1,2,3]
def printListFromTailToHead(self, listNode):
# write code here
result = []
while True:
if listNode == None:
break
result.append(listNode.val)
listNode = listNode.next
result.reverse()
return result
总结：
显式用栈基于循环实现的代码的鲁棒性要要好一些，如果链表较长，就会导致函数调用的层级很深，从而很有可能导致函数调用栈溢出。
递归要把握好，结束条件和返回值，需要更新的操作。