从小白开始刷算法 递归篇 leetcode.206

206. 反转链表

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1

F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

输入：n = 2

输出：1

解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3

输出：2

解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4

输出：3

解释：F(4) = F(3) + F(2) = 2 + 1 = 3

题目来源：力扣（LeetCode）

递归思路

能否写出：写出，但需要思路。

时间：20多分钟想+10分钟看思路

思路：

建议画图，也推荐看 b站up主 爱学习的饲养员 对这题的视频讲解，因为这题用视频理解比文字理解要好，而且up主的对这题的讲解也十分不错。

首先判断链表是否为空或只有一个节点，如果是，则直接返回该节点。

1. 递归调用reverseList函数，传入当前节点的下一个节点作为参数，得到反转后的链表头节点。
2. 将当前节点的下一个节点的next指针指向当前节点，实现反转。
3. 将当前节点的next指针设为null，断开与下一个节点的连接，避免形成循环。
4. 返回反转后的链表头

// 仅是我的思路代码，leetcode上大神更厉害
class Solution {
    public ListNode reverseList(ListNode head) {
        // 基本情况：链表为空或只有一个节点
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);  // 递归反转子链表
        head.next.next = head;  // 反转指针方向
        head.next = null;
        return newHead;  // 返回新的头节点
    }
}

时间复杂度： O(n)

空间复杂度：O(n)

其他思路：

从小白开始刷算法 ListNode 链表篇 leetcode.206