剑指OFFER之从尾到头打印链表

题目描述：

输入一个链表，从尾到头打印链表每个节点的值。

输入：

每个输入文件仅包含一组测试样例。
每一组测试案例包含多行，每行一个大于0的整数，代表一个链表的节点。第一行是链表第一个节点的值，依次类推。当输入到-1时代表链表输入完毕。-1本身不属于链表。

输出：

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

样例输入：

1
2
3
4
5
-1

样例输出：

5
4
3
2
1

Code：

#include <iostream>
#include <stack>
 
using namespace std;
 
struct Node{
    Node *next;
    int data;
};
 
int main()
{
    int val;
    stack<Node*> S;
    Node *head=new Node();
    Node *pre=head;
    cin>>val;
    while(val!=-1){
        Node *current=new Node();
        current->next=NULL;
        current->data=val;
        pre->next=current;
        pre=current;
        cin>>val;
    }
    Node *index=head->next;
    while(index!=NULL){
        S.push(index);
        index=index->next;
    }
    while(S.empty()==false){
        Node *tmp=S.top();
        cout<<tmp->data<<endl;
        S.pop();
    }
    return 0;
}
 
/**************************************************************
    Problem: 1511
    User: lcyvino
    Language: C++
    Result: Accepted
    Time:90 ms
    Memory:5348 kb
****************************************************************/

  

　　既然用到了栈，所以也可以用递归解决这个问题：如果我要打印一个结点的值，那我先打印我的下一个结点值，再打印当前结点。即如果我要逆序打印一个链表的结点，那我就先逆序打印除头结点和第一个结点之外所有的结点，再打印第一个结点。

Code：

#include <iostream>
 
using namespace std;
 
struct Node{
    Node *next;
    int data;
};
 
void ReversePrint(Node *T){
    if(T!=NULL){
        if(T->next!=NULL){
            ReversePrint(T->next);
        }
        cout<<T->data<<endl;
    }
}
 
int main()
{
    int val;
    Node *head=new Node();
    Node *pre=head;
    cin>>val;
    while(val!=-1){
        Node *current=new Node();
        current->next=NULL;
        current->data=val;
        pre->next=current;
        pre=current;
        cin>>val;
    }
    ReversePrint(head->next);  //head是头结点
    return 0;
}
 
/**************************************************************
    Problem: 1511
    User: lcyvino
    Language: C++
    Result: Accepted
    Time:90 ms
    Memory:6044 kb
****************************************************************/