题解 | #反转链表#

题目难度：中等
考察内容：链表
题目内容：输入一个链表，反转链表后，输出新链表的表头。

问题分析
首先较为简单的思路是开辟额外空间，去保存链表然后反转，明显用vector保存反转最为方便，直接用stl里的reverse(v.begin(), v.end());即可
然后链表以此指向每一个元素即可
算法1（构造）
下面给出代码

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if (!pHead) return nullptr;
        //特判空链表
        vector<ListNode*> z;
        //vector记录每个节点
        while (pHead) {
            v.push_back(pHead);
            //记录节点
            pHead = pHead->next;
            //指向下一个节点
        }
        reverse(v.begin(), v.end()); 
        // 直接反转vector

        ListNode *head = v[0];
        ListNode *cur = head;
        for (int i=1; i<v.size(); ++i) { // 构造链表
            cur->next = v[i]; // 当前节点的下一个指针指向下一个节点
            cur = cur->next; // 当前节点后移
        }
        cur->next = nullptr; // 切记最后一个节点的下一个指针指向nullptr
        return head;
    }
};

时间复杂度为O(n)
空间复杂度为O(n)
空间复杂度可以进一步优化
算法2
上图说话

怎么去找到方法指向下一个？ 新定义一个节点先指向下一个即可.

这时候就完成了反转
代码如下

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
    ListNode *h=NULL;
        //记录下一个节点的位置
        ListNode *ans=NULL;
        //记录反转链表
        while(pHead)
        {
            h=pHead->next;
            //h先指向下一个
            pHead->next=ans;
            //下一个指向ans，即一个反转
            ans=pHead;
            //ans往右走
            pHead=h;// 当前节点往右继续走
        }
        return ans;
    }
};