题目描述

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

思路

利用三指针写法，定义三个指针表示前一个结点p、当前节点q、后一个结点tmp，然后每次往后移都让tmp等于q的next，然后更新q的next等于p，之后就是让p=q，q=tmp，这样复杂度为$O(n)$，空间复杂度$O(1)$

#include<bits/stdc++.h>
using namespace std;
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==NULL)return pHead;    //空链表
        ListNode *q=pHead->next,*p=pHead;
        if(q==NULL)return pHead;    //只有一个节点
        pHead->next=NULL;
        while(true){    
            ListNode *tmp=q->next;   //后继节点
            q->next=p;    //将当前节点next指向前一个节点
            if(tmp==NULL)return q;
            p=q;    //更新前一个节点为当前节点
            q=tmp;    //更新当前节点为后一个节点
        }
    }
};
int main(){
    Solution ac;
    ListNode head(1);
    ListNode *root=&head;
    for(int i=2;i<=10;++i){
        root->next=new ListNode(i);
        root=root->next;
    }
    root=&head;
    cout<<ac.ReverseList(root)->val<<endl;
    return 0;
}