[数据结构与算法]【Leetcode链表】206. 反转链表（双指针法和递归法！！）

Leetcode206

1.问题描述

2.解决方案

解法一：双指针法

记住代码的三步走，就可以了
1.保存cur的下一个节点
2.反转操作
3.更新操作

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre= nullptr;
        ListNode* cur=head;
        while(cur!= nullptr){
            //1.保存cur的下一个节点
            ListNode* temp=cur->next;

            //2.反转操作
            cur->next=pre;

            //3.更新操作
            pre=cur;
            cur=temp;
        }
        return pre;
    }
};

解法二：递归法

可以看到，其实和解法一思路一摸一样的，也是记住代码的三步走
1.保存cur的下一个节点
2.反转操作
3.更新操作(递归调用)

class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur==nullptr) return pre;
        //1.保存cur的下一个节点
        ListNode* temp=cur->next;
        
        //2.反转操作
        cur->next=pre;

        //3.更新操作
        //可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
        //pre = cur;
        //cur = temp;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        ListNode* pre= nullptr;
        ListNode* cur=head;
        return reverse(pre,cur);
    }
};