题解 | #反转链表#

一.题目描述
NC78反转链表
题目链接:
https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=188&&tqId=38547&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking
输入一个链表，反转链表后，输出新链表的表头。
二.算法(暴力模拟)
可以先用一个vector将单链表的指针都存起来，然后再构造链表，下面是完整代码:

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(!pHead) return NULL;
        vector<ListNode*>q;
        while(pHead){
            q.push_back(pHead);
            pHead=pHead->next;
        }
        //利用reverse函数对链表进行反转
        reverse(q.begin(),q.end());
        ListNode* h=q[0];
        ListNode* r=h;//尾节点
        //构造链表
        for(int i=0;i<q.size();i++){
            r->next=q[i];
            r=r->next;
        }
        r->next=NULL;
        return h;
    }
};

时间复杂度；o(n)
空间复杂度：o(1)
优缺点：方便实现，但是空间复杂度高

三.算法(双指针)

(1)定义两个指针：pre和cur,pre在前cur在后。
(2)每次让pre的next指向cur,实现一次局部反转
(3)局部反转完成之后,pre和cur同时往前移动一个位置
(4)循环上述过程，直至pre到达链表尾部

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        //开始对两个指针的定义
        ListNode *pre = nullptr;
        ListNode *cur = pHead;
        ListNode *nex = nullptr; //这里可以指向nullptr，循环里面要重新指向
        while (cur) {
            //双指针实现指针方向改变
            nex=cur->next;
            cur->next=pre;
            pre=cur;
            cur=nex;
        }
        return pre;
    }
};

时间复杂度：o(n)
空间复杂度；o(1) 不需要额外空间
优缺点：空间消耗低，但是实现起来麻烦。