递归反转链表的一部分.md

# 递归反转链表的一部分 







<p align='center'>
<a href="https://github.com/labuladong/fucking-algorithm" target="view_window"><img alt="GitHub" src="https://img.shields.io/github/stars/labuladong/fucking-algorithm?label=Stars&style=flat-square&logo=GitHub"></a>
<a href="https://appktavsiei5995.pc.xiaoe-tech.com/index" target="_blank"><img class="my_header_icon" src="https://img.shields.io/static/v1?label=精品课程&message=查看&color=pink&style=flat"></a>
<a href="https://www.zhihu.com/people/labuladong"><img src="https://img.shields.io/badge/%E7%9F%A5%E4%B9%8E-@labuladong-000000.svg?style=flat-square&logo=Zhihu"></a>
<a href="https://space.bilibili.com/14089380"><img src="https://img.shields.io/badge/B站-@labuladong-000000.svg?style=flat-square&logo=Bilibili"></a>
</p>

![](https://labuladong.github.io/algo/images/souyisou1.png)

**通知：[数据结构精品课](https://aep.h5.xeknow.com/s/1XJHEO) 已更新到 V1.9，[第 11 期刷题打卡挑战（9/19 开始）](https://mp.weixin.qq.com/s/eUG2OOzY3k_ZTz-CFvtv5Q) 开始报名。**



读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

| LeetCode | 力扣 | 难度 |
| :----: | :----: | :----: |
| [206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/) | [206. 反转链表](https://leetcode.cn/problems/reverse-linked-list/) | 🟢
| [92. Reverse Linked List II](https://leetcode.com/problems/reverse-linked-list-ii/) | [92. 反转链表 II](https://leetcode.cn/problems/reverse-linked-list-ii/) | 🟠
| - | [剑指 Offer 24. 反转链表](https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/) | 🟢
| - | [剑指 Offer II 024. 反转链表](https://leetcode.cn/problems/UHnkqh/) | 🟢

**-----------**

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

本文就来由浅入深，step by step 地解决这个问题。如果你还不会递归地反转单链表也没关系，**本文会从递归反转整个单链表开始拓展**，只要你明白单链表的结构，相信你能够有所收获。

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

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

看下力扣第 92 题「反转链表 II」：

![](https://labuladong.github.io/algo/images/反转链表/title.png)

**注意这里的索引是从 1 开始的**。迭代的思路大概是：先用一个 for 循环找到第 `m` 个位置，然后再用一个 for 循环将 `m` 和 `n` 之间的元素反转。但是我们的递归解法不用一个 for 循环，纯递归实现反转。

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

### 一、递归反转整个链表

这也是力扣第 206 题「反转链表」，递归反转单链表的算法可能很多读者都听说过，这里详细介绍一下，直接看代码实现：

```java
// 定义：输入一个单链表头结点，将该链表反转，返回新的头结点
ListNode reverse(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}
```

看起来是不是感觉不知所云，完全不能理解这样为什么能够反转链表？这就对了，这个算法常常拿来显示递归的巧妙和优美，我们下面来详细解释一下这段代码。

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

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

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

![](https://labuladong.github.io/algo/images/反转链表/1.jpg)

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

```java
ListNode last = reverse(head.next);
```

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

![](https://labuladong.github.io/algo/images/反转链表/2.jpg)

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

![](https://labuladong.github.io/algo/images/反转链表/3.jpg)

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

现在再来看下面的代码：

```java
head.next.next = head;
```

![](https://labuladong.github.io/algo/images/反转链表/4.jpg)

接下来：

```java
head.next = null;
return last;
```

![](https://labuladong.github.io/algo/images/反转链表/5.jpg)

神不神奇，这样整个链表就反转过来了！递归代码就是这么简洁优雅，不过其中有两个地方需要注意：

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

```java
if (head == null || head.next == null) {
    return head;
}
```

意思是如果链表为空或者只有一个节点的时候，反转结果就是它自己，直接返回即可。

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

```java
head.next = null;
```

理解了这两点后，我们就可以进一步深入了，接下来的问题其实都是在这个算法上的扩展。

### 二、反转链表前 N 个节点

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

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

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

![](https://labuladong.github.io/algo/images/反转链表/6.jpg)

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

```java
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` 连接上。

![](https://labuladong.github.io/algo/images/反转链表/7.jpg)

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

### 三、反转链表的一部分

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

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

首先，如果 `m == 1`，就相当于反转链表开头的 `n` 个元素嘛，也就是我们刚才实现的功能：

```java
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` 呢……

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

```java
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)。所以递归操作链表可以作为对递归算法的练习或者拿去和小伙伴装逼，但是考虑效率的话还是使用迭代算法更好。

> 最后打个广告，我亲自制作了一门 [数据结构精品课](https://aep.h5.xeknow.com/s/1XJHEO)，以视频课为主，手把手带你实现常用的数据结构及相关算法，旨在帮助算法基础较为薄弱的读者深入理解常用数据结构的底层原理，在算法学习中少走弯路。

**＿＿＿＿＿＿＿＿＿＿＿＿＿**

**《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「PDF」可获取精华文章 PDF**：

![](https://labuladong.github.io/algo/images/souyisou2.png)


======其他语言代码======

[92.反转链表II](https://leetcode-cn.com/problems/reverse-linked-list-ii/)



### c++

[shilei](https://github.com/ShileiGuo) 提供C++解法代码:

思想:

   1.head表示需要反转的头节点，pre表示需要反转头节点的前驱节点

   2.对于从m到n的节点反转，需要反转n-m次，将head的next节点移动到需要反转链表部分的首部，需要反转链表部分剩余节点依旧保持相对顺序即可

   3.示例 当m=2, n=5时 

   第一次反转：1(pre) 2(head) 3(next) 4 5 反转为 1 3 2 4 5

   第二次反转：1(pre) 3 2(head) 4(next) 5 反转为 1 4 3 2 5

   第三次发转：1(pre) 4 3 2(head) 5(next) 反转为 1 5 4 3 2

```CPP
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        //初始化哨兵节点
        ListNode* dummy=new ListNode(-1);
        //初始化待反转区间的前一个节点
        ListNode* pre=dummy;
        //哨兵节点下一个节点指向head头节点
        dummy->next=head;
        
        //获取待反转节点的前一个节点
        for(int i=0;i<m-1;i++)
            pre=pre->next;        
        //获取待反转节点的第一个节点
        head=pre->next;  
        //迭代反转n-m次，将head的next节点移动到需要反转链表部分的首部
        for(int i=m;i<n;i++){
            ListNode* t=head->next;       
            head->next=t->next;          
            t->next=pre->next;         
            pre->next=t;                
        }
        //返回哨兵节点
        return dummy->next;
    }
};
```

### python
[DiamondI](https://github.com/DiamondI) 提供python3版本代码：

思路：递归。时间复杂度为O(n)，由于递归调用需要借助栈的空间，因此空间复杂度亦为O(n)。

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
  def __init__(self):
    self.__successor = None

    def __reverseN(self, head: ListNode, n: int) -> ListNode:
      if n == 1:  
        # 记录第 n + 1 个节点
        self.__successor = head.next;
        return head;
      # 以 head.next 为起点，需要反转前 n - 1 个节点
      last = self.__reverseN(head.next, n - 1);

      head.next.next = head;
      # 让反转之后的 head 节点和后面的节点连起来
      head.next = self.__successor;
      return last;

    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
      # base case
      if m == 1:
        return self.__reverseN(head, n);
      # 前进到反转的起点触发 base case
      head.next = self.reverseBetween(head.next, m - 1, n - 1);
      return head;
```



### javascript

**递归反转整个链表**

[206. 反转链表](https://leetcode-cn.com/problems/reverse-linked-list/)

```js
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if (head == null || head.next == null) {
        return head;
    }
    const last = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return last;
};
```



**反转链表前 N 个节点**

这题貌似在leetcode上没找到，就不贴链接了。

```js
let successor = null; // 后驱节点

let reverseListN = function(head, n) {
    if (n === 1) {
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
    }

    // 以 head.next 为起点，需要反转前 n - 1 个节点
    let last = reverseListN(head.next, n - 1);

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



**反转链表的一部分**

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

```js
let successor = null; // 后驱节点

let reverseListN = function(head, n) {
    if (n === 1) {
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
    }

    // 以 head.next 为起点，需要反转前 n - 1 个节点
    let last = reverseListN(head.next, n - 1);

    head.next.next = head;

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

/**
 * @param {ListNode} head
 * @param {number} m
 * @param {number} n
 * @return {ListNode}
 */
let reverseBetween = function(head, m, n) {
    // base case
    if (m === 1) {
        return reverseListN(head, n);
    }
    // 前进到反转的起点触发 base case
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
};
```