5-从尾到头打印链表

题目描写叙述：http://ac.jobdu.com/problem.php?pid=1511
输入一个链表，从尾到头打印链表每一个节点的值。

输入：
每一个输入文件仅包括一组測试例子。

每一组測试案例包括多行，每行一个大于0的整数，代表一个链表的节点。第一行是链表第一个节点的值，依次类推。

当输入到-1时代表链表输入完成。

-1本身不属于链表。

输出：
相应每一个測试案例，以从尾到头的顺序输出链表每一个节点的值。每一个值占一行。

---

逆序打印链表，我们遍历链表仅仅能从头到尾。如今要求我们从尾到头。

后进先出，能够想到用栈存储遍历的节点。然后打印出栈序列。

而递归的本质就是栈结构，在打印本节点之前。先打印本节点的下一个节点。

#include <iostream>
#include <stack>
using namespace std;
class Node {
public:
    int val;
    Node* next;
    Node(int val, Node* next = NULL) {
        this->val = val;
        this->next = next;
    }
};
// 递归实现
void PrintListReversingRecur(Node* head) {
    if (head == NULL)
        return;
    PrintListReversingRecur(head->next);
    cout << head->val << " ";
}
// 栈实现
void PrintListReversingStack(Node* head) {
    stack<Node*> s;
    while (head != NULL) {
        s.push(head);
        head = head->next;
    }
    while (s.empty() == false) {
        cout << s.top()->val << " ";
        s.pop();
    }
    cout << endl;
}
int main() {
    Node* head = new Node(1, new Node(2, new Node(3, new Node(4, NULL))));
    for (Node* iter = head; iter != NULL; iter = iter->next)
        cout << iter->val << " ";
    cout << endl;
    cout << "逆序打印" << endl;
    PrintListReversingRecur(head);
    cout << endl;
    PrintListReversingStack(head);
}

输出结果：
1 2 3 4 
逆序打印
4 3 2 1 
4 3 2 1 
[Finished in 0.4s]