方法1 迭代

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr; // 指向空指针
        ListNode* cur = head;
        ListNode* next = nullptr;
        while(cur){
          next = cur->next;
          cur->next = prev;
          prev = cur;
          cur=next;
        }
        return prev;
    }
};

方法2 递归

要思考这个函数返回的是什么。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        while(!head||!head->next) return head; 
        //!head代表整个链表是空的，不用反转
        //!head->next代表到了最后一个节点，不用反转
        ListNode* tail = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return tail;

    }
};