关于算法-数据结构:递归反转链表的一部分

30次阅读

共计 2763 个字符，预计需要花费 7 分钟才能阅读完成。

读完本文，你能够去力扣拿下如下题目：

92. 反转链表 II

———–

反转单链表的迭代实现不是一个艰难的事件，然而递归实现就有点难度了，如果再加一点难度，让你仅仅反转单链表中的一部分，你是否能 够递归实现 呢？

本文就来由浅入深，step by step 地解决这个问题。如果你还不会递归地反转单链表也没关系，本文会从递归反转整个单链表开始拓展，只有你明确单链表的构造，置信你可能有所播种。

// 单链表节点的构造
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {val = x;}
}

什么叫反转单链表的一部分呢，就是给你一个索引区间，让你把单链表中这部分元素反转，其余局部不变：
e

留神这里的索引是从 1 开始的。迭代的思路大略是：先用一个 for 循环找到第 m 个地位，而后再用一个 for 循环将 m 和 n 之间的元素反转。然而咱们的递归解法不必一个 for 循环，纯递归实现反转。

迭代实现思路看起来尽管简略，然而细节问题很多的，反而不容易写对。相同，递归实现就很简洁柔美，上面就由浅入深，先从反转整个单链表说起。

这个算法可能很多读者都据说过，这里具体介绍一下，先间接看实现代码：

ListNode reverse(ListNode head) {if (head.next == null) return head;
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}

看起来是不是感觉不知所云，齐全不能了解这样为什么可能反转链表？这就对了，这个算法经常拿来显示递归的奇妙和柔美，咱们上面来具体解释一下这段代码。

对于递归算法，最重要的就是明确递归函数的定义。具体来说，咱们的 reverse 函数定义是这样的：

输出一个节点 head，将「以 head 为终点」的链表反转，并返回反转之后的头结点。

明确了函数的定义，在来看这个问题。比如说咱们想反转这个链表：

那么输出 reverse(head) 后，会在这里进行递归：

ListNode last = reverse(head.next);

不要跳进递归（你的脑袋能压几个栈呀？），而是要依据方才的函数定义，来弄清楚这段代码会产生什么后果：

这个 reverse(head.next) 执行实现后，整个链表就成了这样：

并且依据函数定义，reverse 函数会返回反转之后的头结点，咱们用变量 last 接管了。

当初再来看上面的代码：

head.next.next = head;

接下来：

head.next = null;
return last;

神不神奇，这样整个链表就反转过去了！递归代码就是这么简洁优雅，不过其中有两个中央须要留神：

1、递归函数要有 base case，也就是这句：

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

意思是如果链表只有一个节点的时候反转也是它本人，间接返回即可。

2、当链表递归反转之后，新的头结点是 last，而之前的 head 变成了最初一个节点，别忘了链表的开端要指向 null：

head.next = null;

了解了这两点后，咱们就能够进一步深刻了，接下来的问题其实都是在这个算法上的扩大。

这次咱们实现一个这样的函数：

// 将链表的前 n 个节点反转（n <= 链表长度）ListNode reverseN(ListNode head, int n)

比如说对于下图链表，执行 reverseN(head, 3)：

解决思路和反转整个链表差不多，只有稍加批改即可：

ListNode successor = null; // 后驱节点

// 反转以 head 为终点的 n 个节点，返回新的头结点
ListNode reverseN(ListNode head, int n) {if (n == 1) { 
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
    }
    // 以 head.next 为终点，须要反转前 n - 1 个节点
    ListNode last = reverseN(head.next, n - 1);

    head.next.next = head;
    // 让反转之后的 head 节点和前面的节点连起来
    head.next = successor;
    return last;
}

具体的区别：

1、base case 变为 n == 1，反转一个元素，就是它自身，同时 要记录后驱节点。

2、方才咱们间接把 head.next 设置为 null，因为整个链表反转后原来的 head 变成了整个链表的最初一个节点。但当初 head 节点在递归反转之后不肯定是最初一个节点了，所以要记录后驱 successor（第 n + 1 个节点），反转之后将 head 连贯上。

OK，如果这个函数你也能看懂，就离实现「反转一部分链表」不远了。

当初解决咱们最开始提出的问题，给一个索引区间 [m,n]（索引从 1 开始），仅仅反转区间中的链表元素。

ListNode reverseBetween(ListNode head, int m, int n)

首先，如果 m == 1，就相当于反转链表结尾的 n 个元素嘛，也就是咱们方才实现的性能：

ListNode reverseBetween(ListNode head, int m, int n) {
    // base case
    if (m == 1) {
        // 相当于反转前 n 个元素
        return reverseN(head, n);
    }
    // ...
}

如果 m != 1 怎么办？如果咱们把 head 的索引视为 1，那么咱们是想从第 m 个元素开始反转对吧；如果把 head.next 的索引视为 1 呢？那么绝对于 head.next，反转的区间应该是从第 m - 1 个元素开始的；那么对于 head.next.next 呢……

区别于迭代思维，这就是递归思维，所以咱们能够实现代码：

ListNode reverseBetween(ListNode head, int m, int n) {
    // base case
    if (m == 1) {return reverseN(head, n);
    }
    // 后退到反转的终点触发 base case
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}

至此，咱们的最终大 BOSS 就被解决了。

递归的思维绝对迭代思维，略微有点难以了解，解决的技巧是：不要跳进递归，而是利用明确的定义来实现算法逻辑。

解决看起来比拟艰难的问题，能够尝试化整为零，把一些简略的解法进行批改，解决困难的问题。

值得一提的是，递归操作链表并不高效。和迭代解法相比，尽管工夫复杂度都是 O(N)，然而迭代解法的空间复杂度是 O(1)，而递归解法须要堆栈，空间复杂度是 O(N)。所以递归操作链表能够作为对递归算法的练习或者拿去和小伙伴装逼，然而思考效率的话还是应用迭代算法更好。

正文完