翻转链表

本题要求将单链表翻转，我开始的思路是，链表翻转即将最后一个节点作为首节点，然后从后往前依次递推，但很快我发现这很不显示，因为这样需要每次都选择到当前链表的最后一个节点，把它从链表中拿出来，然后再取出倒数第二个节点……这样的时间复杂度就有n^2了

参考了一下牛客官方的题解，我发现我忽略了链表自身的特性，即创建链表不一定就用尾插法，也可以采用首插法，而本题在已经给出的链表的情况下，采用首插法将大大降低复杂度

首插法的方法，就是取出现需要处理链表的头结点，作为我们需要翻转链表的头结点，那么按照这样的操作，需要处理链表的尾节点就是它的头结点

思路很简单，需要注意的也就是三个位置，1.需要处理链表的头部，定义pHead指向它，2.需要处理链表的第二个节点定义next指向它（方便后续操作），3.所得翻转链表的头部，定义pre指向它；

代码如下

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(!pHead) return nullptr;
        ListNode* pre,* next;
        pre = pHead;
        next = pHead->next;
        pre->next = nullptr;
        while(next){
            pHead = next;    //新一***作中原有的第二个节点即为原链表的首节点
            next = pHead->next;
            pHead->next = pre;    //将该头结点指向所得翻转链表头部
            pre = pHead;    //更新头部位置
        }
        return pre;
    }
};