struct Node
{
    int data;
    Node* pNext;
};

class ListEx
{
private:
    Node *m_pHead;
    Node *m_pTail;
public:
    ListEx()
    {
        m_pHead = NULL;
        m_pTail = NULL;
    }
    ~ListEx()
    {
        Node *pNode = m_pHead;
        Node *pNext = NULL;
        while(pNode)
        {
            pNext = pNode->pNext;
            delete pNode;
            pNode = pNext;
        }

        m_pHead = NULL;
        m_pTail = NULL;
    }
    void add(int data)
    {
        Node *pNode = new Node;
        pNode->data = data;
        pNode->pNext = NULL;

        if (!m_pHead)
        {
            m_pTail = m_pHead = pNode;
        }
        m_pTail->pNext = pNode;
        m_pTail = pNode;
    }

    Node* GetHead() {return m_pHead;}

    // 改变链表的内容，将其逆序
    void ReserveList()
    {
        m_pTail = m_pHead;
        Node *p1 = m_pHead;
        Node *p2 = p1->pNext;
        p1->pNext = NULL;        //关键位置
        Node *pTemp = NULL;     
        while (p1 && p2)
        {
            pTemp = p2->pNext;   // 关键位置
            p2->pNext = p1;
            p1 = p2;
            p2 = pTemp;
        }

        m_pHead = p1;
    }
};

// 从尾打印链表
void PrintList(Node *pHead)
{
    stack<int> NodeStack;
    Node *pNode = pHead;
    while (pNode)
    {
        NodeStack.push(pNode->data);
        pNode = pNode->pNext;
    }
    
    while (!NodeStack.empty())
    {
        cout << NodeStack.top();
        NodeStack.pop();
    }
    cout << endl;
}

void main()
{
    ListEx list;
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    list.add(6);
    list.add(7);
    list.add(8);
    list.add(9);

    Node *pHead = list.GetHead();
    cout << "不修改原列表，使用stack方法：" << endl;
    PrintList(pHead);
    list.ReserveList();

    cout << "修改原列表，将原列表逆序：" << endl;
    pHead = list.GetHead();
    PrintList(pHead);
    return;
}