输入一个链表，反转链表后，输出新链表的表头。

有两个思路，在代码里写清楚了

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};

/*
思路1：利用栈先进后出的特性。
遍历链表并将节点一一进栈，接着栈内元素一一出栈并覆盖原链表的值。
*/
ListNode* ReverseList_1(ListNode* pHead)
{
    if (pHead == nullptr)
        return nullptr;

    stack<int>listStack;
    ListNode* p = pHead;
    while (p!=nullptr)
    {
        listStack.push(p->val);
        p = p->next;
    }

    p = pHead;
    while (!listStack.empty() && p != nullptr)
    {
        int stack_val = listStack.top();
        listStack.pop();
        p->val = stack_val;
        p = p->next;

    }
    return pHead;
}

/*
思路2：只需遍历一遍就实现链表反转。
设置三个指针pNode,pPrev,pNext,分别表示当前指针，前驱指针，后继指针。
pNode改变方向指向pPrev,为防止链表断裂，设置pNext记录后一个节点
*/
ListNode* ReverseList_2(ListNode* pHead)
{
    if (pHead == nullptr)
        return nullptr;
    ListNode* pNode = pHead, * pNext = pNode->next, * pPrev = nullptr;
    while (pNode != nullptr)
    {
        pNext = pNode->next;
        pNode->next = pPrev;
        pPrev = pNode;
        pNode = pNext;
    }
    pHead = pPrev;
    return pHead;
}