方法一：新建链表

1.结题思路

看到这道题，最容易想到的应该就是保存链表指针或者权值，构造新的链表，题目是简单题，很容易AC。

2.解法

vector容器保存节点指针。然后先令头指针指向最后一个结点，从倒数第二个元素开始反向遍历vector，后插法建立新的链表。

3.图解

4.具体代码

ListNode* ReverseList(ListNode* pHead) {
    if(pHead==NULL||pHead->next==NULL)return pHead;
    vector<ListNode*>v;//保存所有指针
    while(pHead){
        v.push_back(pHead);//指针依次放入vector
        pHead=pHead->next;//指针后移
    }
    ListNode *head=v[v.size()-1],*p=head;//p为当前结点 
    for(int i=v.size()-2;i>=0;i--){//在p结点（倒数第一结点）后依次加入倒数第二，第三结点..... 
        p->next=v[i];//修改当前结点next指针指向
        p=p->next;//指针后移
    } 
    p->next=NULL;//最后一个结点的后继指向NULL 
    return head;
}

5.时间复杂度和空间复杂度分析

时间复杂度：O(n)，n为结点数，仅仅对所有结点进行了正反两次遍历。

空间复杂度：O(n)，n为结点数，仅使用了vector来存储n个结点。

方法二：反转next指针

1.结题思路

常规思路，遍历链表的同时，如果知道该结点前驱及后继结点，则直接将该结点next指针反向，然后不断使当前结点next反向，最后遍历结束时，即构造出一个反向链表。

2.解法

• 设立三个指针
  p:从头结点开始向后遍历
  p_next:指向p的下一结点
  p_pre:指向p的前一结点
  从头到尾进行遍历，并使当前结点next指针反向,再使得三指针依次后移。

• 观察得，每次操作之后p_pre及其之前的结点都已经完成反转，所以处理完所有结点的反转后，p_pre指向原先链表的最后一个结点，即循环解除条件应该为pre->next==NULL,也即p==NULL

• 在倒数第二次后移完成时，p_pre指向倒数第二结点，p指向最后一个结点，p_next指向NULL，所以p_next指针后移的需加上判断条件：当前p_next还未指向NULL。

3.图解

4.具体代码

ListNode* ReverseList(ListNode* pHead) {
    if(pHead==NULL||pHead->next==NULL)return pHead;//返回带头结点空链表,一开始没写pHead==NULL，WA了一波 
    ListNode *p=pHead,*p_next=pHead->next,*p_pre=NULL;//三指针初始化 
    while(p){//或p_pre->next!=NULL
        p->next=p_pre;//当前结点next指针反向
        p_pre=p;p=p_next;if(p_next!=NULL)p_next=p_next->next;//三指针依次后移
    } 
    return p_pre; 
}

5.时间复杂度和空间复杂度分析

时间复杂度：O(n)，n为结点数，仅对所有结点进行一次遍历

空间复杂度：O(1)，未用到额外的存储容器存储