题解 | #反转链表#

方法一：

• 将链表中的值提取出来，然后分配新的链表节点组成新链表。

  代码如下：

  class Solution {
  public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode *p,*t;
        int q;
        //存链表节点的值
        stack<int> s;
        p=pHead;
        //遍历链表，将链表节点的值压栈
        while(p!=NULL){
            s.push(p->val);
            p=p->next;
        }
        ListNode* ret=new ListNode(0);
        p=ret;
        //从栈中取出节点值重新分配节点并构建新链表
        while(!s.empty()){
            q=s.top();
            s.pop();
            t=new ListNode(q);
            p->next=t;
            p=t;
        }
        return ret->next;
    }
  };

  复杂度分析：

  时间复杂度：O(n)，遍历。
  空间复杂度：O(n)，额外分配的链表节点。

方法二：

• 针对方法一的提取链表的值进行改进，通过在栈中存储节点指针来反转链表。

  代码如下：

  class Solution {
  public:
    ListNode* ReverseList(ListNode* pHead) {
        //存储链表节点指针的栈
        stack<ListNode*> s;
        ListNode* p=pHead;
        //遍历链表，将节点指针压栈
        while(p!=NULL){
            s.push(p);
            p=p->next;
        }
        //newHead为新链表的辅助节点。
        ListNode* newHead=new ListNode(0),*tail=newHead;
        //从栈中取出链表节点指针，并构建新的链表
        while(!s.empty()){
            ListNode* tmp=s.top();
            s.pop();
            tail->next=tmp;
            tail=tmp;
        }
        tail->next=nullptr;
        return newHead->next;
    }
  };

  复杂度分析：

  时间复杂度：O(n)，遍历。
  空间复杂度：O(n)，额外n个指针的栈空间。

方法三：

• 对链表进行一次遍历，遍历时将当前节点插入新链表表尾，同时更新原链表表头为下一个节点。

  图解如下：

  

  代码如下：

  class Solution {
  public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==nullptr) return nullptr;
        //newHead为反转后链表的表头。将原链表分离出来首节点为新的链表。
        ListNode* newHead=pHead;
        pHead=pHead->next;
        newHead->next=nullptr;
  
        //从原链表中循环分离出首节点，并插入新链表的头部。
        while(pHead!=nullptr){
            ListNode* tmp=pHead;
            pHead=pHead->next;
            tmp->next=newHead;
            newHead=tmp;
        }
        return newHead;
    }
  };

  复杂度分析：

  时间复杂度：O(n)，遍历。
  空间复杂度：O(1)，仅常数个临时变量。