剑指offer——面试题6：从尾到头打印链表

#include"iostream"
#include"stdio.h"
#include"stack"
using namespace std;

struct ListNode
{
    int value;
    ListNode *pNext;
};

ListNode* CreatListNode(int x)
{
    ListNode *pNode=new ListNode();
    pNode->pNext=nullptr;
    pNode->value=x;

    return pNode;
}

//头指针是指向指针的指针，不然会出错
void AddNewNode(ListNode **pHead,ListNode *pNode)
{
    if(*pHead==nullptr)
    {
        *pHead=pNode;
        return;
    }
    ListNode *pTemp=*pHead;
    while(pTemp->pNext!=nullptr)
    {
        pTemp=pTemp->pNext;
    }
    pTemp->pNext=pNode;
}

void PrintList(ListNode *pHead)
{
    if(pHead==nullptr)
    {
        cout<<"empty list!"<<endl;
        return;
    }
    ListNode *pNode=pHead;
    stack<int> allNode;
    while(pNode!=nullptr)
    {
        allNode.push(pNode->value);
        pNode=pNode->pNext;
    }
    while(!allNode.empty())
    {
        cout<<allNode.top()<<" ";
        allNode.pop();
    }
    cout<<endl;
}
//递归输出
void PrintListRecursively(ListNode *pHead)
{
    if(pHead!=nullptr)
    {
        if(pHead->pNext!=nullptr)
        {
            PrintListRecursively(pHead->pNext);
        }
        cout<<pHead->value<<" ";
    }
}

void Test(ListNode *pHead)
{
    PrintList(pHead);
}

//1->2->3->4->5
void Test1()
{
    cout<<"Test1 begins:";
    ListNode **pHead=new ListNode*();
    *pHead=nullptr;
    AddNewNode(pHead,CreatListNode(1));
    AddNewNode(pHead,CreatListNode(2));
    AddNewNode(pHead,CreatListNode(3));
    AddNewNode(pHead,CreatListNode(4));
    AddNewNode(pHead,CreatListNode(5));
    PrintList(*pHead);
    cout<<endl;
}

//1
void Test2()
{
    cout<<"Test2 begins:";
    ListNode **pHead=new ListNode*();
    *pHead=nullptr;
    AddNewNode(pHead,CreatListNode(1));
    PrintList(*pHead);
    cout<<endl;
}
//nullptr
void Test3()
{
    cout<<"Test3 begins:";
    ListNode **pHead=new ListNode*();
    *pHead=nullptr;
    PrintList(*pHead);
    cout<<endl;
}

int main()
{
    Test1();
    Test2();
    Test3();
    return 0;
}

通过在尾部添加元素创建链表时，一定要记住pHead是指向指针的指针，否则出了这个函数pHead仍然为nullptr。