206题

方法一：使用栈，先把数据压进栈中，再依次弹出

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL||head->next==NULL){
            return head;
        }
        ListNode* result=NULL;
        ListNode* temp=NULL;
        stack<int>s;
        while(head){
            s.emplace(head->val);
            head=head->next;
        }
        while(!s.empty()){
            int a=s.top();
            s.pop();
            auto curnode=new ListNode(a);
            if(!temp){
                result=curnode;
                temp=result;
            }else{
                temp->next=curnode;
                temp=temp->next;
                }
            }
            return result;
        }
};

方法二：递归

class Solution {
public:
    ListNode* result;
    ListNode* reverseList(ListNode* head) {
        if(head==NULL||head->next==NULL){
            return head;
        }
        ListNode* a=reverseList(head->next);
        ListNode* temp=a;
        while(a->next){
            a=a->next;
        }
        a->next=head;
        head->next=NULL;
        return temp;
    }
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

方法三：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* curr=head;
        ListNode* a1=NULL;
        while(curr){
            ListNode* next1=curr->next;
            curr->next=a1;
            a1=curr;
            curr=next1;
        }
        return a1;
    }
};