面试题5：从尾到头打印链表

链表是由指针把若干个结点连接成链状结构，是一种动态的数据结构。在创建链表时，无须知道链表的长度，当插入一个结点时，只需为新节点分配内存，然后调整指针的指向。由于链表是按需分配内存的，故其空间效率比较高。

面试题5：从尾到头打印链表

//题目描述 // //输入一个链表，从尾到头打印链表每个节点的值。 // //输入描述: //输入为链表的表头 // // // //输出描述: //输出为需要打印的"新链表"的表头 #include<iostream> #include<vector> #include<stack> #include<windows.h> using namespace std; struct ListNode {         int val;         struct ListNode *next;       ListNode(int x) :              val(x), next(NULL) {        } }; // 栈的思想 // 0ms 8552k class Solution { public:     vector<int> printListFromTailToHead(struct ListNode* head) {         stack<int>s=stack<int>(); while(head!=NULL){ s.push(head->val); head=head->next; } vector<int>res=vector<int>(s.size()); int k=0; while(!s.empty()){ res[k++]=s.top(); s.pop(); } return res;     } }; // 0ms 8568k class Solution { public:     vector<int> printListFromTailToHead(struct ListNode* head) {         vector<int>res=vector<int>(); stack<int>s=stack<int>(); while(head!=NULL){ s.push(head->val); head=head->next; } while(!s.empty()){ res.push_back(s.top()); s.pop(); } return res;     } }; // 递归思想 // 0ms 8552k class Solution { public:     vector<int> printListFromTailToHead(struct ListNode* head) {         vector<int>res=vector<int>(); if(head!=NULL){ res=printListFromTailToHead(head->next); res.push_back(head->val); } return res;     } };

递归在本质上就是一个栈结构。但当链表很长时，就会导致函数调用的层级很深，从而可能导致函数调用栈溢出，显式用栈基于循环实现的鲁棒性好一些。

已使用 Microsoft OneNote 2010 创建
一个用于存放所有笔记和信息的位置