剑指offer-JZ15

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

两种思路：暴力法，双指针法；

方法一：暴力
利用vector 保存每一个链表指针，然后逆向构建。
时间复杂度：
空间复杂度：
代码如下：

 class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        // empty
        if(pHead == nullptr) return nullptr;
        //save listnode
        vector<ListNode*> vec;
        while(pHead != nullptr){
            vec.push_back(pHead);
            pHead = pHead->next;
        }
        //reverse(vec.begin(),vec.end());
        // create new head
        int n = vec.size()-1;
        ListNode *new_head = vec[n];
        ListNode *current = new_head;
        for(int i=n-1; i>=0; i--){
            current->next = vec[i];
            current = current->next;
        }
        current->next = nullptr;
        return new_head;
    }
};

方法二： 双指针法
利用两个相邻指针，维护更新连接的指向，从头至尾。
时间复杂度：
空间复杂度：
代码如下：

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        // empty
        if(!pHead) return nullptr;
        // creat two pointer;
        ListNode *pre = nullptr;
        ListNode *cur = pHead;
        ListNode *nex;
        while(cur){
            // save next point;
            nex = cur->next;
            // change current point;
            cur->next = pre;
            // update three point
            pre = cur;
            cur = nex;
        }
        return pre;
    }
};