虽然用递归来解答反转链表的题型会使得程序的调用多了一层隐式压栈、消耗额外的内存空间，但此类题型用递归来解答确实会使整个代码看起来分外优雅，不得不说，递归的魅力让人欲罢不能、又爱又恨。。。接下来就从206.反转链表到反转第N个节点（非力扣题目），再到92.反转链表|| ，一层一层剖开反转链表题型的套路。

leetcode 206. 反转链表

---

示例： 1→2→3→4

反转结果：4→3→2→1

反转链表四步走：

1. 代码1处：此部分是我们常说的递归中的base case，条件是如果当前节点是尾节点，就直接返回；

   （注意：判定尾节点的是条件：head.next == null，而第一个条件head == null只是为了过防止传入head=null的测试用例）

2. 代码2处：此部分是我们常说的drill down，逻辑为：如果当前节点不是尾节点，那么继续找尾节点，我们拿示例来逐一drill down（不推荐下探太多层，不然会把自己搞懵了）；

3. 代码3、4处：找到尾节点后，就可以开始处理当前节点了：

   3.1（代码3处） 将当前节点的下下个节点指针指向自己，此为反转。从例子来分析，当递归第一次在第2处代码返回newHead时，head为3（因为下一层的4.next==null条件成立）。这一步翻译成大白话：3.next.next=3，完成4→3。

   3.2（代码4处） 断开3的next指针，不再指向4，到这就完成了3和4两个节点的反转。（至于3指向2这一步是在何时完成？实际上就是在本层处理完并回溯至上一层后，上一层重复步骤3.1时完成的。）

4. 代码4处：最终我们返回最后一个节点，即为反转后的头节点（示例中为节点4）。这一步也很多同学会看懵，为啥newHead就是我们要的？仔细想想，最后一个节点newHead是在我们第一次进入代码1 处时返回的，而在第一次返回之后，虽然newHead被一层一层往上传，但上层的代码并不会改动这个newHead的指向，所以我们可以放心地认为newHead就是最后一个节点。

public ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;// 1
        }
        ListNode newHead = reverseList2(head.next);// 2
        head.next.next = head;// 3
        head.next = null;// 4
        return newHead;// 5
}

看完链表反转的代码，再想一想，如果我们要反转第1到第N个节点的子链表，应该怎么反转？还是用递归来解答，为了反转后可以衔接上原有的母链表，我们需要在找到子链表的尾节点N时，记录一下第N+1个节点，这样在完成反转后，我们就可以让原来的头节点head（也就是反转后的尾节点，示例中为：节点1 ）的next指针指向这N+1个节点（示例中为：节点5），具体看下图：

image.png

代码如下：

// 第N+1个节点
ListNode lastNext = null;

private ListNode reverseN(ListNode head, int n) {
    if (n == 1) {
        lastNext = head.next;
        return head;
    }
    ListNode newHead = reverseN(head.next, n - 1);
    head.next.next = head;
    // 将原来的head的next指向原来的第N+1个节点
    head.next = lastNext;
    return newHead;
}

可以发现，除了加一个N+1节点的记录指针lastNext，以及最终head.next指向N+1节点，其他代码总体框架跟原先的反转链表是一样的。

leetcode 92. 反转链表||

---

示例

image.png

反转链表||这道题要求我们反转left到right段的子链表，我们就可以用reverseN的思想来解答，代码如下：

class Solution {

    public ListNode reverseBetween(ListNode head, int left, int right) {
      if (left == 1) {
          // 沿用reverseN方法
          return reverseN(head, right);
      }
      head.next = reverseBetween(head.next, left - 1, right - 1);
      return head;
    } 

    // 第N+1个节点（为了明确这个变量是给下面这个方法用的，把变量的定义放在这- -）
    ListNode lastNext = null;

    private ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            lastNext = head.next;
            return head;
        }
        ListNode newHead = reverseN(head.next, n - 1);
        head.next.next = head;
        // 将原来的head的next指向原来的第N+1个节点
        head.next = lastNext;
        return newHead;
    } 

}

结合代码和示例，可以看到，我们在下探到下一层时，只要让left和right一直保持同步减1，同时让head一直遍历下一个节点，那么总有一个时刻left会等于1，而当left=1时：

1、此时head的指向刚好就是我们要进行反转的头节点（所以left其实是充当了一个计数器的角色，它告诉head应该走几次next指针才能到达我们想要开始反转的位置）。

2、此时的right刚好就是reverseN中所需要的参数N。

最后，我们将原本的头节点的next指针，指向新的头节点，即可返回答案。