剑指offer：反转链表

题目描述：

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

解题思路：

思路一：先遍历一次链表，将每个结点存入栈中，再清空栈，构造新的链表，当前结点的下一个结点都为从栈新取出的结点，同时结点后移，指向这个新取出的结点。例如，用tmp表示新链表，cur = s.top(); cur->next = nullptr; tmp->next = cur. 注意需要判断当前栈中结点数量，若取完栈顶元素后无栈为空，则不再更新tmp = tmp->next。

思路二：看了一下网上有更简单清晰的思路，用三个指针来维护整个链表，cur指向当前结点，pre指向前一个结点，nex指向后一个结点。

代码：

思路一：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==nullptr)
            return pHead;
        ListNode *new_pHead, *tmp, *cur;
        tmp = pHead;
        stack<ListNode*> s;
        while(tmp!=nullptr)
        {
            s.push(tmp);
            tmp = tmp->next;
        }
        tmp = s.top();
        s.pop();
        new_pHead = tmp;
        while(!s.empty())
        {
            cur = s.top();
            cur->next = nullptr;
            s.pop();
            tmp->next = cur;
            if(s.size()>0)
                tmp = tmp->next;
        }
        return new_pHead;        
    }
};

思路二：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==nullptr)
            return pHead;
        ListNode *cur, *pre, *nex, *new_pHead;
        pre = nullptr;
        cur = pHead;
        while(cur!=nullptr)
        {
            nex = cur->next;
            if(nex == nullptr)
                new_pHead = cur;
            
            cur->next = pre;
            pre = cur;
            cur = nex;
        }
        return new_pHead;
    }
};