学步园

58.从尾到头输出链表。
题目：输入一个链表的头结点，从尾到头反过来输出每个结点的值。链表结点定义如下：
struct ListNode
{
int  m_nKey;
ListNode* m_pNext;
};

/*
58.从尾到头输出链表。
题目：输入一个链表的头结点，从尾到头反过来输出每个结点的值。链表结点定义如下：
struct ListNode
{
	int  m_nKey;
	ListNode* m_pNext;
};

1：借用栈倒序输出链表
  　因为栈是先进后出，把链表中的元素存进栈中，链表前面的元素在栈底，后面的元素在栈顶，链表后面的元素先出栈

2：先翻转链表，再顺序输出
	就是单链表的翻转
    翻转链表的步骤：
        1:将当前节点的next节点指向他以前的前一个节点
        2:当前节点下移一位
        3:如果是最后一个节点，就把它的next节点指向它以前的前一个节点，并推出循环

3：递归实现
	同栈 
*/

#include<iostream> 
#include<stdio.h> 
#include<string>  
#include<stack>
using namespace std;  

struct node  
{   
    int date;  
    struct node *next;   
};    
 
 
void create(node **Head,int date)  
{  
    node *p=new node();
	p->date=date;
	 
    if(!(*Head))  
    {   
        *Head=p;  
    }  
    else  
    {    
        p->next=(*Head);  
        (*Head)=p;  
    }  
} 

void print(node *head)  
{  
    while(head)  
    {  
        cout<<head->date<<" ";  
        head=head->next;  
    }  
    cout<<endl;  
}   
 
/* 方法1: 利用栈实现 */  
void reverseOutput1(node* head)  
{  
    node* p=head;
	stack<int> s;
	   
    while(p!=NULL)  
    {  
        s.push(p->date);  
        p=p->next;  
    }  
    while(!s.empty())  
    {  
        printf("%d  ",s.top()); 
		s.pop(); 
    }  
    printf("\n");  
}  
  
/* 方法2: 先链表逆序,再遍历输出 */  
void reverseList(node* head)  
{  
	node *p=head,*previous=NULL,*next=NULL;
	
	while(p->next!=NULL)
	{
		next=p->next;//保存下一个 
		p->next=previous;//p下一个为他前面的
		previous=p;
		p=next; 
	}
	p->next=previous;
    while(p!=NULL)  
    {  
        printf("%d  ", p->date);  
        p=p->next;  
    }  
    printf("\n");   
}   
 
/* 方法3: 递归调用 */  
void reverseOutput3(node* head)   
{  
    if(!head)  
        return; 
    reverseOutput3(head->next);  
    printf("%d  ", head->date);   
}  

int main() {  
    node *head=NULL; 
	create(&head,9);  
	create(&head,7);   
    create(&head,5);  
    create(&head,4);  
    create(&head,3);  
    create(&head,2);  
    create(&head,1);  
    cout<<"原链表数据："<<endl; 
    print(head);  //1 2 3 4 5 7 9
    
    cout<<"方法1: 利用栈实现 逆置结果："<<endl; 
    reverseOutput1(head);
    cout<<"方法3: 递归调用 逆置结果："<<endl; 
	reverseOutput3(head);
	cout<<endl;
	cout<<"方法2: 先链表逆序,再遍历输出 逆置结果："<<endl; 
    reverseList(head);
    
    //方法3放最后 因为把链表逆置了，或者再逆置回来 
    return 0;  
}