题解 | #反转链表#

题意思路：

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

方法一：调整链表指针，反转链表

pre指针指向已经反转好的链表的最后一个节点，初始化为null；

cur指针指向待反转链表的第一个节点，最开始第一个节点待反转，所以指向头指针；

next指针指向待反转链表的第二个节点，目的是保存链表，因为cur改变指向后，后面的链表则失效了，所以需要保存

图解：

复杂度分析

时间复杂度：O(N)，N链表的长度，遍历链表；

空间复杂度：O(1)，未开辟新空间.

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
           ListNode *pre=NULL;//pre指针指向已经反转好的链表的最后一个节点，初始化为null；
            ListNode *cur=pHead;//cur指针指向待反转链表的第一个节点，最开始第一个节点待反转，所以指向头指针；
            ListNode *next=NULL;//next指针指向待反转链表的第二个节点，目的是保存链表，因为cur改变指向后，后面的链表则失效了，所以需要保存
           while(cur){
               next=cur->next;//next保存待反转指针的第一个节点
               cur->next=pre;//cur的第一个节点保存已经反转好的链表的最后一个节点
               pre=cur;//已经反转好的链表的最后一个节点保存待反转链表的第一个节点
               cur=next;//待反转链表的第一个节点为反转指针的第一个节点
           }//使指针反转
        return pre;
    }
};

方法二：栈

利用栈先进后出的性质达到反转的目的

复杂度分析

时间复杂度：O(N)，N链表的长度，遍历链表；

空间复杂度：O(N)，栈存储与读取链表节点数据。

代码：

/*
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 *res=NULL;
            ListNode *cur=pHead;
            stack<ListNode*>st;
            while(cur!=NULL){//将链表push栈中 
                st.push(cur);//利用栈先进后出的性质达到反转的目的
                cur=cur->next;
            }
            res=st.top();
            st.pop();
            ListNode *pre=res;
           for(;st.size();st.pop()){//构建链表
               pre->next=st.top();
               pre=pre->next;
           }
        pre->next=NULL;//最后一个节点的下个指针指向NULL
        return res;
    }
};