c++实现---反转链表_反转链表c++实现

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

方法一：构造链表
如果此类型的题出现在笔试中，如果内存要求不高，可以采用如下方法：
可以先用一个vector将单链表的指针都存起来，反转之后再构造链表。
###代码：
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if(pHead==nullptr){
return nullptr;//如果链表为空则返回nullptr
}
vector<ListNode*>res;
while(pHead){
res.push_back(pHead);
pHead=pHead->next;
}
reverse(res.begin(),res.end());
ListNode* head=res[0];//这里注意需要保存一个反转后指向头节点的head指针，一个从head出发的cur指针
ListNode* cur=head;
for(int i=1;i<res.size();i++){
cur->next=res[i];// 当前节点的下一个指针指向下一个节点
cur = cur->next; // 当前节点后移
}
cur->next = nullptr; // 切记最后一个节点的下一个指针指向nullptr
return head;

}
1

};

时间复杂度：O(n)
空间复杂度：O(n), 用了一个vector来存单链表
方法二：三指针优化解法（更好）
初始化：3个指针
1）pre指针指向已经反转好的链表的最后一个节点，最开始没有反转，所以指向nullptr
2）cur指针指向待反转链表的第一个节点，最开始第一个节点待反转，所以指向head
3）nex指针指向待反转链表的第二个节点，目的是保存链表，因为cur改变指向后，后面的链表则失效了，所以需要保存
代码

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==nullptr){
            return nullptr;//如果链表为空则返回nullptr
        }
        ListNode* pre=nullptr;//定义一个指向nullptr的pre指针
        ListNode* pNode=pHead;//初始化一份pHead的拷贝
        while(pNode){
            ListNode* pNext=pNode->next;//每一次循环记录当前结点的下一个节点
            pNode->next=pre;//当前结点指向前一个（第一次指向的时nullptr）
            pre=pNode;//将pre指针和pNode指针同时后移
            pNode=pNext;
        }
        return pre;//返回pre指针即可

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

时间复杂度：O(n), 遍历一次链表
空间复杂度：O(1)