给你看一张知乎截图

五分钟学算法

发布于 2023-09-30 14:16:34

3370

发布于 2023-09-30 14:16:34

文章被收录于专栏：五分钟学算法

大家好，我是吴师兄。

先给大家看一张图，知乎上回复量挺多的一个提问：会写递归超越了多少程序员？

在这个话题下，回答者们旗帜鲜明的分为了两派：

1、会写递归就和学英语学会了 ABC 那么简单。

2、会写递归，至少超越了 50% 甚至 90% 的程序员。

我搜了一下我的微信聊天记录，惊讶的发现，每一周都有算法训练营的学员问我和递归相关的算法题，很多时候，同学们明明上一周搞懂了，这一周却又绕不出来了。

递归还是挺难的一个算法知识点。

我在回答他们问题的时候，非常喜欢用反转链表这道题目来举例子和分析。

给大家看一段可以解决反转链表这道算法题的递归代码。

class Solution {
    public ListNode reverseList(ListNode head) {
        // 寻找递归终止条件
        // 1、head 指向的结点为 null 
        // 2、head 指向的结点的下一个结点为 null 
        // 在这两种情况下，反转之后的结果还是它自己本身
        if( head == null || head.next == null) return head;

        // 不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点
        // 因为到最后一个节点的时候，由于当前节点 head 的 next 节点是空，所以会直接返回 head
        ListNode cur =   reverseList(head.next);

        // 比如原链表为 1 --> 2 --> 3 --> 4 --> 5
        // 第一次执行下面代码的时候，head 为 4，那么 head.next = 5
        // 那么 head.next.next 就是 5.next ，意思就是去设置 5 的下一个节点
        // 等号右侧为 head，意思就是设置 5 的下一个节点是 4
        
        // 这里出现了两个 next
        // 第一个 next 是「获取」 head 的下一节点
        // 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值
        head.next.next = head;

        // head 原来的下一节点指向自己，所以 head 自己本身就不能再指向原来的下一节点了
        // 否则会发生无限循环
        head.next = null;

        // 我们把每次反转后的结果传递给上一层
        return cur;

    }
}

去掉注释阅读的话，就只有 5 行代码。

class Solution {
    public ListNode reverseList(ListNode head) {
      
        if( head == null || head.next == null) return head;

        ListNode cur =   reverseList(head.next);

        head.next.next = head;

        head.next = null;
      
        return cur;
    }
}

万变不离其宗，绝大部分递归的代码都和上述的代码类似，或者也是如下图所示。