勇闯算法-递归法拿下反转链表的三杀

前言

编程语言：Java（JDK8）

单链表节点类：

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

关于反转链表，有迭代和递归两种实现方式，本文使用递归实现反转。

首先介绍递归的思想，然后从最基本的反转整个单链表开始，由浅入深，最终拿下反转链表的“三杀”！

递归思想

任何一个问题，如果能够用迭代解决，那么一定可以转换成递归。 —— 某算法大神

我们很难去证明大神的说法不正确，但我们可以先假设他的理论成立。先强行让自己接受。

恩！没错！能够用迭代解决就一定能用递归解决！

是不是有递归“内味”了？先假设条件成立，把主要逻辑走通。

那么到底如何将迭代转换成递归呢？

迭代是遍历，一个一个地进行迭代处理；

而递归呢？在处理第一个的时候要先假设后面的全部都处理完了，只需处理第一个，所以，只要第一个处理完了，整个就处理完了（感觉完全无法接受啊）。

“假设”始终是假设，但是它能让我们的当前逻辑走通。在第一次的假设中，我们可以进行第二次地假设，假设后面的数据的第一个之后的数据全都处理完了，则只需处理此时的第一个。这样不停地假设下去，直到假设到整体的最后一个数据，这个时候没有数据让我们假设了，不能再“骗自己”了！要拿出点真本事来！我们对整体的最后一个数据进行真实的处理，这个时候我们发现，倒数第二个数据的假设成立了！多米偌骨牌效应！之前所有的假设都成立了！问题解决了！

`First Blood`：反转整个单链表

首先用递归来解决最基本的整个单链表的反转。（“对面辅助开始搞事情了”）

例如：单链表为：1 -> 2 -> 3 -> 4 -> 5 -> null，那么反转之后的单链表为：null <- 1 <- 2 <- 3 <- 4 <- 5。

对应上面的递归思想：在反转第一个节点的时候，先假设后面的节点全都反转完了，返回了反转后的头节点，它就是整个单链表反转完成后的头节点，于是我们只需将第一个节点进行反转，整个链表的反转就完成了。在第一次假设中，同样进行假设，不停地假设，直到最后一个节点，后面没有节点让我们进行假设了，我们进行真实的反转。这时之前所有的假设像多米偌骨牌一样地成立了，整个单链表反转完成！

好像无法理解？没关系，按递归的思想，先假设自己理解了。我们来看下代码：

public static ListNode reverse(ListNode head) {
    // 最后一个节点
    if (head.next == null)
        // 不能再“骗自己”了
        return head;
    // 假设后面的节点全都反转完成，返回了反转后的头节点，即为整个单链表反转后的头节点
    ListNode reverseHead = reverse(head.next);
    // 反转第一个节点
    head.next.next = head;
    head.next = null;
    // 返回反转后的头节点
    return reverseHead;
}

reverse函数的定义是这样的：输入一个节点head，将以head为头节点的链表反转，返回反转后的头节点。

我们要反转的链表为：1 -> 2 -> 3 -> 4 -> 5 -> null：

reverse(1)：输入第一个节点1时；

假设后面的节点已经反转完成并返回了反转后的头节点：ListNode reverseHead = reverse(head.next);

后面的节点反转后的结果为：null <- 2 <- 3 <- 4 <- 5，返回的头节点reverseHead为5；

此时我们只需要对节点1进行反转：

// 将节点1的下一个节点2的指针域指向节点1
head.next.next = head;
// 将节点1的下一个节点指向null
head.next = null;

整个链表的反转就完成了！

但是我们不能“骗自己”！reverse函数不停地进行假设，当它接收到原链表的最后一个节点时，没有节点进行假设了，必须去反转！

由于只有一个节点，反转后还是自身，所以我们只需返回该节点，即为反转后的头节点。这时我们惊奇的发现前面所有的假设都成立了！

这就是所谓的递归的出口：

1 2	if (head.next == null) return head;

我们画张图来看下整个流程。

我们的递归算法只需要关注原链表的第一个节点（头节点）和最后一个节点（尾节点），也就是递归开始的节点和无法再进行假设的节点。在递归函数中，首先要处理尾节点，因为这是不可再假设的节点；当处理头节点时，我们进行假设，假设头节点之后的所有节点都已完成反转同时返回了反转后的新头节点，然后对头节点进行反转，此时就完成了整个单链表的反转。

学会了递归思想后，我们就可以愉快的开始“三杀”之旅了！

`Double Kill`：反转单链表的前`N`个节点

有了上面的“一血”，“双杀”简直就是白送！（“辅助死了，ADC开始送了”）

我们要实现的函数如下：

/**
 * 将单链表的前n个节点进行反转。（n <= 单链表长度）
 * @param head 单链表头节点
 * @param n 前n个节点
 */
public ListNode reverseN(ListNode head,int n) {...}

假设我们要反转单链表的前3个元素，那我们要实现的效果如下图所示：

按照递归思想，我们只需要关注递归开始的节点和无法再进行假设的节点：即头节点和第N个节点。

对于原单链表的头节点，先假设其后面的N - 1个节点已经反转完成并返回了反转后的新头节点，此时我们只需要反转头节点，将头节点指向第N + 1个节点，链表前N个节点的反转就完成了。但是此时第N + 1个节点我们无法得知。

由于单链表的特性，我们只有遍历到第N个节点时才能得到第N + 1个节点，那我们有必要单独对链表进行遍历获取第N + 1个节点吗？

完全没必要！因为我们的递归算法本身一开始就要处理第“N”个节点，因为它是无法再进行假设的节点，所以，递归函数中第一步处理第“N”个节点时要记录下第N + 1个节点（使用全局变量）。注意：这里的第N个节点是针对原单链表而言的；对于最后一个无法再进行假设的假设来说：N = 1。

于是我们就可以完成对原链表头节点的反转。从而完成整个单链表的前N个节点反转：

/**
 * 记录原链表的第N+1个节点
 */
static ListNode nNext;

public static ListNode reverseN(ListNode head,int n) {
    if (n == 1) {
        // 记录原链表的第 n + 1 个节点
        nNext = head.next;
        // 无法再进行假设了，返回反转后的头节点
        return head;
    }
    // 假设后面节点的前 N - 1 个节点已经完成了反转，并返回了反转后的新头节点
    ListNode reverseHead = reverseN(head.next,n - 1);
    // 反转原链表的头节点
    head.next.next = head;
    head.next = nNext;
    // 返回反转后的新头节点
    return reverseHead;
}

“双杀”拿下，不知道你有没有掌握到递归的套路？（“此时对面打野赶到下路，即将送出三杀”）

`Triple Kill`：反转单链表的第`m`个到第`n`个节点

给定单链表的索引区间[m,n]（约定不越界），反转此区间内的节点。（“敌方打野正在路上”）

已知条件为：单链表的头节点和区间m、n的值，我们要实现的函数如下：

/**
 * 反转从m到n之间的节点。1 <= m < n <= 链表长度
 * @param head 原链表头节点
 * @param m 反转开始节点
 * @param n 反转结束节点
 */
public static ListNode reverseBetweenMToN(ListNode head,int m,int n);

例如：单链表为：1 -> 2 -> 3 -> 4 -> 5 -> null，m = 2, n = 4，那么反转之后的单链表为：1 -> 4 -> 3 -> 2 -> 5 -> null。

按照递归的思想，我们在处理头节点head时，先假设后面的节点已经反转完成并返回了反转后的新头节点，那么只需将头节点的指针域指向反转后的新头节点就完成了需求。

对于去除头节点head之后的链表，我们需要反转的是从m - 1到n - 1区间内的节点：

1 2	head.next = reverseBetweenMToN(head.next,m - 1,n - 1); return head;

那按照递归思想，我们什么时候不能再“骗自己”了呢？当假设到原链表的第m个节点时，对于这个假设来说，是这个假设的第1个节点，此时这个假设需要反转从第1个到第n - m + 1 = n个节点，这不正是Double Kill中的反转单链表的前N个节点吗？

于是递归函数完整实现为：

public static ListNode reverseBetweenMToN(ListNode head,int m,int n) {
    if (m == 1) {
        return reverseN(head,n);
    }
    head.next = reverseBetweenMToN(head.next,m - 1,n - 1);
    return head;
}