NC78 反转链表（数组）

NC78 反转链表（数组） 描述

给定一个单链表的头结点pHead，长度为n，反转该链表后，返回新链表的表头。
要求：空间复杂度 O(1)，时间复杂度 O(n) 。

解题思路

方法一：可以先用一个vector将单链表的指针都存起来，然后再构造链表。

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(!pHead) return nullptr;
        vector v;
        while(pHead){
            v.push_back(pHead);
            pHead=pHead->next;
        }
        reverse(v.begin(),v.end());
        ListNode* head = v[0];
        ListNode* cur=head;
        for(int i=1;inext=v[i];
            cur=cur->next;
        }
        cur->next=nullptr;
        return head;
    }
};

方法二：调整链表指针
初始化：3个指针
（1) pre指针指向反转好链表的头节点，最开始指向空
（2) cur指针指向待反转的第一个结点，最开始指向原来链表的头节点
（3) next指针指向待反转的第二个结点，目的是保存链表，因为cur改变指向后，后面的链表就失效了，所以需要保存。
接下来，循环执行以下三个 *** 作
1）nex = cur->next, 保存作用
2）cur->next = pre 未反转链表的第一个节点的下个指针指向已反转链表的最后一个节点
3）pre = cur， cur = nex; 指针后移， *** 作下一个未反转链表的第一个节点
循环条件，当然是cur != nullptr
循环结束后，cur当然为nullptr，所以返回pre，即为反转后的头结点

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(!pHead) return nullptr;
        ListNode* pre = nullptr;
        ListNode* cur = pHead;
        ListNode* next = nullptr;
        while(cur){
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};