如何理解递归算法

  • 相信递归
  • 小例子验证

比如leetcode206：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

img

1
2
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

img

1
2
输入：head = [1,2]
输出：[2,1]

示例 3：

1
2
输入：head = []
输出：[]

提示：

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {

        // 定义基线条件
        if (head == null || head.next == null) {
            return head;
        }
        // 表示下个节点起的链表都是已经反转好的
        ListNode last = reverseList(head.next);
        // 那么，当前节点该怎么处理？
        // 1、现将当前节点链到反转链表的后面（因为last是反转链表的头，所以不能写成last.next= head）
        head.next.next = head;
        // 2、与原链表进行断开
        head.next = null;
        return last;
    }
}

1、相信递归

明确函数reverseList的意义：表示当链表的下一个节点起，都是反转好的，我该怎么处理？

也就是当执行完成ListNode last = reverseList(head.next);之后，last就是一个反转好的链表；

2、小例子验证

当得到一个反转好的链表之后，我该怎么处理？

如下：

1
2
3
4
5
6
7
// 表示下个节点起的链表都是已经反转好的
ListNode last = reverseList(head.next);
// 那么，当前节点该怎么处理？
// 1、现将当前节点链到反转链表的后面（因为last是反转链表的头，所以不能写成last.next= head）
head.next.next = head;
// 2、与原链表进行断开
head.next = null;
  • 第一步：现将当前节点链到反转链表的后面，切记不能写成last.next= head，因为last是反转链表的头，并不是尾；
  • 第二步：当前节点与原链表进行断开；