从尾到头打印链表

题目：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。

思路1:使用栈

思路2:递归

#include<iostream>
#include <stdlib.h>
#include <stack>

using namespace std;

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

ListNode* CreateListNode(int value)
{
    ListNode *pNode = new ListNode();
    pNode->m_nValue = value;
    pNode->m_pNext = NULL;
    return pNode;
}

void PrintListNode(ListNode* pNode)
{
    printf("%d\n", pNode->m_nValue);
}

//打印链表
void PrintList(ListNode* pHead)
{
    ListNode* pNode = pHead;
    while(pNode != NULL)
    {
        cout << pNode->m_nValue<<" ";
        pNode=pNode->m_pNext;
    }
    cout << endl;
}

//在链表结尾添加一个结点
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;
    }

}

//方法1: 用栈实现
void PrintListReversingly_Iteratively(ListNode* pHead)
{
    ListNode* pNode = pHead;
    stack<ListNode*> nodes;

while(pNode != NULL)
    {
        nodes.push(pNode);
        pNode = pNode->m_pNext;
    }

while(!nodes.empty())
    {
        pNode = nodes.top();
        cout<<pNode->m_nValue<<" ";
        nodes.pop();
    }
    cout << endl;
}

//方法2: 递归
void PrintListReversingly_Recursively(ListNode* pHead)
{
    ListNode* pNode = pHead;
    if(pNode != NULL)
    {
        if(pNode->m_pNext != NULL)
            PrintListReversingly_Recursively(pNode->m_pNext);
    }
    cout<<pNode->m_nValue<<" ";
}

// 1->2->3->4->5->6->7
int main()
{
    ListNode* pNode1 = CreateListNode(1);
    PrintList(pNode1);

AddToTail(&pNode1,2);
    AddToTail(&pNode1,3);
    AddToTail(&pNode1,4);
    AddToTail(&pNode1,5);
    AddToTail(&pNode1,6);
    AddToTail(&pNode1,7);

PrintList(pNode1);
   
    PrintListReversingly_Iteratively(pNode1);
    PrintListReversingly_Recursively(pNode1);
   
    return 0;
}