【LC】反转链表

---

题目描述

题解一：置换数据（栈）

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr)
            return nullptr;
        
        ListNode* ptr = head;
        ListNode* res = head;   //返回值
        //使用stack
        stack<int> st;
    
        while(head != nullptr)
        {
            st.push(head->val);
            head = head->next;
        }
    
        while(!st.empty())
        {
            ptr->val = st.top();
            st.pop();
            ptr = ptr->next;
        }
        return res;
    }
};

注意：当然也可以置换结构：但是需要注意最后一个节点的next需要设置NULL，防止有环

---

题解二：pre cur next指针

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr) return nullptr;
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* next = nullptr;

        while(cur != nullptr)
        {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
       
        return pre;
    }
};

注意：指针改变的次序，防止指针跑丢

---

题解三：递归

注意：递推过程找尾结点，回归过程改变next域

class Solution {
public:
    ListNode* reverse(ListNode* p)
    {
        if(p == NULL || p->next == NULL)
        {
            return p;
        }
        ListNode* last = reverse(p->next);
        p->next->next = p;
        p->next = NULL;
        return last;
    }
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr)
            return nullptr;

        ListNode* ptr = head;
        head = reverse(ptr);
        return head;
    }
};