力扣-206-反转链表/剑指Offer-24

如果要一次顺序遍历中反转每个节点的next指针指向，那么在反转之前得把next指针先保存下来，不然就无法继续向下遍历，这就是迭代中循环第一步
而递归中是另一个思路：层层嵌套向下遍历，直到链表的最后一个元素，再向前进行操作，这样就不需要保存下一个节点了
其实类比迭代，递归也是操作head、head->next、head->next->next三个变量

迭代

想要顺序遍历，反转链表，当操作一个节点时，我们还需要知道：

1. 它的前一个节点，用以指向
2. 它的后一个节点，由于继续向后遍历

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 迭代
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while(cur!=nullptr){
            ListNode* next = cur->next;
            // 初始化写到里面来，cur->next可能不存在
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

递归

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr||head->next==nullptr){
            // 这里的head->next其实是当前节点的下下个节点
            return head;
        }
        ListNode* newNode = reverseList(head->next);
        // 到这里会不断追寻下一个节点，直到到达最后一个节点
        // 然后依次向前进行以下过程
        head->next->next = head;
        head->next = nullptr;
        return newNode;
    }
};