输入一个链表，从尾到头打印链表每个节点的值。
输入描述：输入为链表的表头
输出描述：输出为需要打印的“新链表”的表头
一、问题分析
初拿到这个题目时，这应该是考察单向链表这一数据结构。单向链表的遍历总是从头指针逐项遍历各个节点，现在要求从尾到头打印节点的值，我们可以在遍历时把各节点压入栈内，最后出栈打印各个节点值，即可达到要求。
实现之前，我们先来看看如何创建一个链表。
1，链表节点的数据结构定义
1 struct ListNode {
2 int val;
3 struct ListNode *next;
4 ListNode(int x) :
5 val(x), next(NULL) {
6 }
7 };
在链表的定义中，包含自己的整形成员（当然也可以定义为其它数据类型，如double），以及下一个节点的位置信息（next）。这里我们还定义了节点的构造函数（ListNode），方便节点的初始化。
2，链表的创建
这里我们考虑单向链表。如果通过用户输入来创建链表，我们可以进行如下操作：
1)创建头节点head，指向NULL。因为此时没有任何节点
2）为加入的节点分配空间，赋初值（如1中考虑的int类型）并指向NULL。判断head==NULL?head指向该节点：“上一节点”指向该节点
3）更新新加入的节点为“上一节点”
4）判断节点是否添加结束，若否，重复2,3,4步骤继续添加节点。
二、问题的解决思路
1，利用stack反转输出链表节点值
#include <iostream>
#include <vector>
#include <stack>
using namespace std; //链表节点定义
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
}; //链表从尾到头输出节点值方法实现
class Solution {
public:
//方法1，通过stack 这个container来实现反转链表
vector<int> printListFromTailToHead(struct ListNode* head) {
vector<int> result;
if(head == NULL)
return result;
stack<ListNode*> reverse;
ListNode* node = head;
while(node != NULL) {
reverse.push(node);
node = node->next;
}
while(!reverse.empty()) {
node = reverse.top();
result.push_back(node->val);
reverse.pop();
}
return result;
}
//方法2，原地反转链表，不介入其它container
//不断的使“下一个节点”指向“前一个”节点
vector<int> printListFromTailToHead2(struct ListNode* head) {
vector<int> vec;
ListNode *buf = head;
ListNode *pre = buf;
if(head == NULL)
return vec;
while(head->next != NULL){
buf = head->next;
head->next = buf->next;
buf->next = pre;
pre = buf;
}
while(buf){
vec.push_back(buf->val);
buf = buf->next;
}
return vec;
}
}; struct ListNode* CreateListNode(struct ListNode* head) {
struct ListNode *p1, *p2;
int i = ;
p1 = p2 = (struct ListNode*)malloc(sizeof(ListNode));
cout << "Please input the 1st node, it's address is p1_addr = " << p1 << endl;
cout << "And input -1 to quit.";
cin >> (p1->val);
p1->next = NULL; while (p1->val != -) {
if (NULL == head) {
head = p1;
}
else
p2->next = p1;
p2 = p1;
p1 = (struct ListNode*)malloc(sizeof(ListNode));
++i;
cout << "Please input the " << i << " node," << "it's address is p" << i << "_addr = " << p1 <<endl;
cin >> (p1->val);
}
free(p1);
p2->next = NULL;
p1 = NULL;
cout << "End of creating ListNode." << endl;
return head;
} int main () {
std::vector<int> v;
struct ListNode* head = NULL;
head = CreateListNode(head); Solution s;
v = s.printListFromTailToHead2(head);
for (int var : v) {
cout << var << ' ';
} //测试节点的初始化，与本题无关
struct ListNode myListNode();
cout << myListNode.val << endl; }
上述程序在gcc version 6.1.0下编译通过。
在上面的程序中，实现反转的方法有两个：
1）利用stack先入后出的特性实现链表的反转
2）不借用其它container，不断的使“后一个”节点指向“前一个节点”来原地反转链表。下面来谈谈原地反转链表
2，原地反转链表
我们看函数printListFromTailToHead2()。首先，我们先定义两个指针(buf, pre)，并与head共同指向链表的头节点。然后，通过head->next遍历原始链表，并同时更新buf指向已经遍历到的节点(buf = head->next)，而这期间head始终指向头节点。然后，更新head—>next指向buf的下一个节点(head->next = buf->next)。接着，通过buf->next = pre, 使buf指向前一个节点，紧接着更新pre，使其指向当前节点，以便下一轮更新。
当head->next遍历完链表后，buf指向了原始链表最后一个节点，head->next的值变为了NULL。现在从buf开始遍历，即可反向遍历链表。