从尾到头打印链表

题目描述：

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

输入：

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

输出：

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

样例输入：

1
2
3
4
5
-1

样例输出：

5
4
3
2
1

分析：

很容易想到荣栈来实现；

其实也可以用递归来实现，递归的本质就是一个栈结构；

如果链表特别长，会导致函数调用的层级很深，从而有可能导致函数调用栈溢出；

现实用栈来实现循环的点吗更容易懂；

#include<iostream>
#include<stack>
#include<cstdio>
#include "list.h"
using namespace std;

void PrintListReversingly_Iteratively(ListNode *pHead)
{
	std::stack<ListNode*> nodes;
	ListNode *pNode=pHead;
	while(pNode!=NULL)
	{
		nodes.push(pNode);
		pNode=pNode->m_pNext;
	} 
	while(!nodes.empty())
	{
		pNode=nodes.top();
		printf("%d\t",pNode->m_nValue);
		nodes.pop();
	}
} 

void PrintListReversingly_Recursively(ListNode *pHead)
{
	if(pHead!=NULL)
	{
		if(pHead->m_pNext!=NULL)
		{
			PrintListReversingly_Recursively(pHead->m_pNext);
		}
		printf("%d\t",pHead->m_nValue);
	}
}

void Test(ListNode* pHead)  
{  
    PrintList(pHead);  
    PrintListReversingly_Iteratively(pHead);  
    printf("\n");  
    PrintListReversingly_Recursively(pHead);  
}  

void Test1()  
{  
    printf("\nTest1 begins.\n");  
  
    ListNode* pNode1 = CreateListNode(1);  
    ListNode* pNode2 = CreateListNode(2);  
    ListNode* pNode3 = CreateListNode(3);  
    ListNode* pNode4 = CreateListNode(4);  
    ListNode* pNode5 = CreateListNode(5);  
  
    ConnectListNodes(pNode1, pNode2);  
    ConnectListNodes(pNode2, pNode3);  
    ConnectListNodes(pNode3, pNode4);  
    ConnectListNodes(pNode4, pNode5);  
  
    Test(pNode1);  
  
    DestroyList(pNode1);  
}  
// 只有一个结点的链表: 1  
void Test2()  
{  
    printf("\nTest2 begins.\n");  
  
    ListNode* pNode1 = CreateListNode(1);  
  
    Test(pNode1);  
  
    DestroyList(pNode1);  
}  
  
// 空链表  
void Test3()  
{  
    printf("\nTest3 begins.\n");  
  
    Test(NULL);  
}  
 
 ListNode * CreateListNode(int value)
{
	ListNode *pNode=new ListNode();
	pNode->m_nValue=value;
	pNode->m_pNext=NULL;
	
	return pNode;
}
void ConnectListNodes(ListNode* pCurrent, ListNode* pNext) 
{
	if(pCurrent==NULL)
	{
		printf("Error to connect nodes");
		return;
	}
	
	pCurrent->m_pNext=pNext;
}

void PrintListNode(ListNode* pNode) 
{
	if(pNode ==NULL)
		printf("node is null");
	else
		printf("the key node is %d.\n",pNode->m_nValue); 
}

void PrintList(ListNode* pHead) 
{
	printf("PrintList starts.\n");
	
	ListNode *pNode =pHead;
	while(pNode!=NULL)
	{
		printf("%d\t",pNode->m_nValue);
		pNode=pNode->m_pNext;
	}
	
	printf("\nprintList is ends\n");
}

void DestroyList(ListNode* pHead)  
{
	ListNode *pNode=pHead;
	while(pNode!=NULL)
	{
		pHead=pHead->m_pNext;
		delete pNode;
		pNode =pHead;
		
	}
	pNode=NULL;
}

void AddToTail(ListNode** pHead, int value)
{
	ListNode *pNew=new ListNode();
	pNew->m_nValue=value;
	pNew->m_pNext=NULL;
	
	if(*pHead==NULL)
		*pHead=pNew;
	else
	{
		ListNode *pNode=*pHead;
		while(pNode->m_pNext!=NULL)
			pNode=pNode->m_pNext;
			
		pNode->m_pNext=pNew; 
	}
}
void RemoveNode(ListNode** pHead, int value)  
{
	if(pHead==NULL||*pHead==NULL)
		return;
	ListNode * pToBeDeleted=NULL;
		
	if((*pHead)->m_nValue==value)
	{
		pToBeDeleted=*pHead;
		*pHead=(*pHead)->m_pNext;
	}
	else
	{
		ListNode *pNode=*pHead;
		
		while(pNode->m_pNext != NULL && pNode->m_pNext->m_nValue != value)  
            pNode = pNode->m_pNext;
            
        if(pNode->m_pNext!=NULL&&pNode->m_pNext->m_nValue==value)
		{
			pToBeDeleted = pNode->m_pNext;
			pNode->m_pNext = pNode->m_pNext->m_pNext;
		}
	}
	
	if(pToBeDeleted!=NULL)
	{
		delete pToBeDeleted;
		pToBeDeleted=NULL;
	}
} 
int main()  
{  
    Test1();  
    Test2();  
    Test3();  
  
    return 0;  
}  

list.h

#ifndef _List_H_  
#define _List_H_ 

struct ListNode
{
	int m_nValue;
	ListNode *m_pNext;
};

ListNode * CreateListNode(int value);
void ConnectListNodes(ListNode* pCurrent, ListNode* pNext);  
void PrintListNode(ListNode* pNode);  
void PrintList(ListNode* pHead);  
void DestroyList(ListNode* pHead);  
void AddToTail(ListNode** pHead, int value);  
void RemoveNode(ListNode** pHead, int value);  
#endif /*_List_H_*/  

结果：