利用递归方法实现链表反转、前N个节点反转以及中间部分节点反转

2020 年 9 月 5 日
笔记

一、反转整个链表

问题：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

//单链表的实现结构
public class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x;}
}

反转链表利用迭代不难实现，如果使用递归则有些许难度。

首先来看源码实现：

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

是否看起来不知所云，而又被这如此简洁的代码所震撼？让我们一起探索一下其中的奥秘。

对于递归算法，最重要的是明确递归函数的定义。

我们的reverse函数的定义如下：

输入一个节点head,将以head为起点的链表反转，并返回反转之后的头节点。

明白了函数的定义后，在来看这个问题。比如我们想反转这个链表

那么输入reverse（head）后，会在ListNode ret = reverse(head.next);进行递归

不要跳进递归！（你的脑袋能压几个栈呀？）

根据reverse函数的定义，函数调用后会返回反转之后的头节点，我们用变量ret接收

现在再来看一下代码

head.next.next = head;

接下来：

head.next = null;
return ret;

再跳出这层递归就会得到：

神不神奇，这样整个链表就反转过来了！

递归代码就是这么简洁优雅，但要注意两个问题：

1、递归函数要有base case，不然就会一直递归，导致栈溢出

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

即链表为空或只有一个节点，直接返回

2、当链表递归反转后，新的头节点为ret,而head变成了最后一个节点，应该令链表的某尾指向null

head.next = null;

理解这两个问题之后，我们可以进一步深入研究链表反转的问题，接下来的问题其实均为在这个算法上的扩展。

二、反转链表前N个节点

接下来我们来看这个问题：

问题：反转链表前N个节点，并返回链表头节点

说明：1 <= N <= 链表长度

示例:

输入: 1->2->3->4->5->NULL, n = 4
输出: 4->3->2->1->5->NULL

解决思路和反转整个链表差不多，只需稍加修改

ListNode successor = null; // 后驱节点（第 n + 1 个节点）

ListNdoe reverseN(ListNode head, int n) {
  if (n == 1) {
    successor = head.next;
    return head;
  }
  // 以 head.next 为起点，需要反转前 n - 1 个节点
  ListNode ret = reverseN(head.next, n - 1);
  head.next.next = head;
  head.next = successor; // 将反转后的 head 与后面节点连接
  return ret;
}

具体区别：

1、base case 变为n == 1, 同时需要记录后驱节点。

2、之前把head.next 设置为null,因为整个链表反转后，head变为最后一个节点。

现在head节点在递归反转后不一定为最后一个节点，故应记录后驱successor(第 n + 1 个节点), 反转之后将head连接上。

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

三、反转链表的一部分

现在我们开始解决这个问题，给一个索引区间[m, n]（索引从1开始），仅仅反转区间中的链表元素。

说明：1 <= m <= n <= 链表长度

示例：

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

猛一看很难想到思路。

试想一下，如果m == 1,就相当于反转链表的前 n 元素嘛，也就是我们刚才实现的功能：

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

那如果m != 1 该怎么办？

如果把head的索引视为1，那么我们是想从第m个元素开始反转；

如果把head.next的索引视为1，那么我们是想从第m - 1 个元素开始反转；

如果把head.next.next的索引视为1，那么我们是想从第m - 2 个元素开始反转；

……

区别于迭代思想，这就是递归的思想，所以我们可以完成代码：

ListNode reverseBetween(ListNode head, int m, int n) {
  // base case
  if (m == 1) {
    return reverseN(head, n);
  }
  // 递归前进到触发 base case （m == 1）
  head.next = reverseBetween(head.next, m - 1, n - 1);
  return head;
}

至此，我们终于干掉了大BOSS！