反转链表

## 反转整个链表

> 题目来源：[206. 反转链表](https://leetcode.cn/problems/reverse-linked-list)

### 题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

**示例 1：**

![](https://notebook.ricear.com/media/202206/2022-06-25_1107090.8604224978183835.png)

```txt
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
```

**示例 2：**

![](https://notebook.ricear.com/media/202206/2022-06-25_1107180.5052359862891712.png)

```txt
输入：head = [1,2]
输出：[2,1]
```

**示例 3：**

```txt
输入：head = []
输出：[]
```

**提示：**

* 链表中节点的数目范围是 [0, 5000]
* -5000 <= Node.val <= 5000

**进阶：** 链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

### 问题解析

1. 对于这种包含子问题的题目，我们可以采用**递归**的方法来解决：
   
   1. 首先定义一个递归函数 `reverse(ListNode head)`，用于**将链表反转并返回反转后链表的头部**。
   2. 对于 `reverse()` 函数的返回结果，我们用 `last` 来进行接收，即 `last = reverse(head.next);`。
   3. 接着**将反转后的节点与前面的节点进行连接**，即 `head.next.next = last; head.next = null;`。
   4. 通过以上操作，我们便可以将一个链表进行反转，同时需要注意一下边界条件，因为方法中涉及到 `head.next` 和 `head.next.next` 操作，所以我们需要**对 `head` 和 `head.next` 进行空值判断**：
      
      1. 当 `head == null` 时，说明头结点为空，其反转后的节点肯定也为空，所以直接返回 `null`。
      2. 当 `head.next == null` 时，说明只有这一个节点，反转后肯定还是这个节点，所以直接返回 `head`。
      
      > 上面两个判断条件可以合并为 `if (head == null || head.next == null) {return head;}`
   5. 详细的步骤如下图所示。
      ![](https://notebook.ricear.com/media/202206/2022-06-23_162605_029486.gif)

### 参考代码

```java
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {return head;}
    ListNode last = ReverseList(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}
```

## 反转链表的一部分

> 题目来源：[92. 反转链表 II](https://leetcode.cn/problems/reverse-linked-list-ii)

### 题目

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

**示例 1：**

![](https://notebook.ricear.com/media/202206/2022-06-23_193822_198011.png)

```txt
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
```

**示例 2：**

```txt
输入：head = [5], left = 1, right = 1
输出：[5]
```

**提示：**

* 链表中节点数目为 n
* 1 <= n <= 500
* -500 <= Node.val <= 500
* 1 <= left <= right <= n
  
  进阶： 你可以使用一趟扫描完成反转吗？

### 2.2 问题分析

1. 假设**以 `head` 为基点**，反转链表的一部分对应的函数为 `reverseBetween(head, m, n)`，则如果**以 `head.next` 为基点的话**，反转链表的一部分对应的函数为 `reverseBetween(head.next, m - 1, n - 1)`，因此当**m 减小到 1**时，可以转化为**反转链表的前 $N$ 个节点**，假设其对应的函数为 `reverseN(head, n)`，因此当我们**求出反转链表的前 $N$ 个节点后的链表**，然后**与开始反转的节点之前的一部分链表进行拼接便可得到最后的结果**，因此我们现在的重点就是求**反转链表的前 $N$ 个节点**：
   
   1. 反转前 $N$ 个节点与反转整个链表类似，不同的是**反转整个链表中最后作为尾节点的 $head$ 节点指向空节点**，而**反转链表前 $N$ 个节点最后作为局部尾节点的 $head$ 节点需要指向 $N + 1$ 个节点**。
      
      ![](https://notebook.ricear.com/media/202206/2022-06-23_200107_440593.png)
      
      ~~~java
      ListNode last = reverseN(head.next, n - 1);
      head.next.next = head;
      head.next = sucessor;
      ~~~
   2. 当 `reverseN(head, n)` 中的 `n = 1` 时，此时 `head` 指向要**反转节点的最后一个节点**（这里指的是 4），因此后继节点 `sucessor` 等于 `head.next`，此时直接返回 `head` 即可。
      
      > 需要注意的是 `sucessor` 需要定义为**全局变量**，而不能放在 `reverseN()` 方法内部。
      > 
      > ~~~java
      > public static ListNode sucessor = null;
      > ~~~
      
      ~~~java
      if (n == 1) {
          sucessor = head.next;
          return head;
      }
      ~~~
   3. 反转链表的前 $N$ 个节点的详细解法如下图所示。
      ![](https://notebook.ricear.com/media/202206/2022-06-24_091709_683306.gif)
2. 反转链表的一部分的详细解法如下图所示。
   ![](https://notebook.ricear.com/media/202206/2022-06-24_092119_624442.gif)

### 参考代码

```java
public static ListNode sucessor = null;

/**
 * 92.反转链表 II
 *
 * @param head  单链表的头指针
 * @param left  起始位置
 * @param right 结束位置
 * @return 反转后的单链表
 */
public static ListNode reverseBetween(ListNode head, int left, int right) {
    //  如果 left == 1，则情况转变为反转前 N 个节点
    if (left == 1) {return reverseN(head, right);}
    //  前进到反转的起点触发 base case
    head.next = reverseBetween(head.next, left - 1, right - 1);
    return head;
}

/**
 * 反转前 N 个节点
 * @param head  单链表的头指针
 * @return  反转后的单链表
 */
public static ListNode reverseN(ListNode head, int n) {
    //  如果输入的 head 为 null，则返回 null
    if (head == null) {return null;}
    //  记录第 n + 1 个节点
    if (n == 1) {
        sucessor = head.next;
        return head;
    }

ListNode last = reverseN(head.next, n - 1);
    head.next.next = head;
    head.next = sucessor;
    return last;
}
```

## K 个一组反转链表

> 题目来源：[25. K 个一组翻转链表](https://leetcode.cn/problems/reverse-nodes-in-k-group/)

### 题目

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

**示例 1：**

```txt
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
```

**示例 2：**

```txt
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
```

**提示：**

- 链表中的节点数目为 n
- 1 <= k <= n <= 5000
- 0 <= Node.val <= 1000

**进阶：** 你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

### 问题分析

1. 解答此题时我们按照如下思路进行：
   
   1. 首先**对这一组 $K$ 个链表进行反转**。
   2. 判断一下**这一次反转的链表的长度是否大于**$K$：
      
      1. 如果**大于**$K$ 的话，说明**后面还有元素**，因此**继续反转下一组**$K$**个链表**，并**将反转后的结果与上一组**$K$**个链表进行拼接**。
      2. 如果**小于**$K$ 的话，说明这一组是**链表最后的元素**，由于这一组链表**已经反转过了**，而题目要求的是如果**链表中剩余元素小于**$K$ 的话，需要**保持原来的顺序**，因此**需要对这一组链表进行再次反转**，这样才能保持原来的顺序，最后同样需要**将反转后的结果与上一组**$K$**个链表进行拼接**。
   3. 反转的关键步骤如下图所示。
      
      > - $target$: **每一组反转后的头结点**。
      > - $head$: **每一组反转后的尾节点**。
      > - $p$：**下一组反转的头结点**。
      > - $q$: **临时节点**。
      
      > 每次反转的时候直接返回当前 **头结点** $target$ 即可，最后返回的第一层 $target$ 即是最终的结果。
      
      1. 第一组反转前：
         ![](https://notebook.ricear.com/media/202206/2022-06-24_113834_193774.png)
      2. 第一组反转后：
         ![](https://notebook.ricear.com/media/202206/2022-06-24_113912_678097.png)
      3. 第二组反转前：
         ![](https://notebook.ricear.com/media/202206/2022-06-24_113936_639374.png)
      4. 第二组反转后：
         ![](https://notebook.ricear.com/media/202206/2022-06-24_114004_224175.png)
      5. 第三组反转前：
         ![](https://notebook.ricear.com/media/202206/2022-06-24_114032_804868.png)
      6. 第三组反转后：
         ![](https://notebook.ricear.com/media/202206/2022-06-24_114053_194534.png)
      7. 最终结果：
         
         > 最终结果返回第一层的 $target$，即 $target_1$。
         
         ![](https://notebook.ricear.com/media/202206/2022-06-24_114258_385866.png)
   4. 反转的详细步骤如下图所示。
      ![](https://notebook.ricear.com/media/202206/2022-06-24_114835_395136.gif)

### 参考代码

```java
/**
 * 25. K 个一组翻转链表
 * @param head  头结点
 * @param k 指定节点个数
 * @return  翻转后的链表
 */
public ListNode reverseKGroup(ListNode head, int k) {
    return reverseK(head, k, k+1);
}

/**
 * 翻转链表的前 k 个元素
 * @param head  头结点
 * @param k 指定节点个数
 * @param left  剩余节点个数
 * @return  反转后的链表
 */
public ListNode reverseK(ListNode head, int k, int left) {
    if (head == null || left <= k) {return head;}
    int num = 1;
    ListNode p = head, q = head, target = null;
    while (num <= k && p != null) {
        q = p;
        p = p.next;
        q.next = target;
        target = q;
        num++;
    }
    if (num <= k) {
        return reverse(target);
    } else {
        head.next = reverseK(p, k, num);
    }
    return target;
}
```

## 参考文献

1. [206. 反转链表](https://leetcode-cn.com/problems/reverse-linked-list)。
2. [92. 反转链表 II](https://leetcode-cn.com/problems/reverse-linked-list-ii)。
3. [25. K 个一组翻转链表](https://leetcode-cn.com/problems/reverse-nodes-in-k-group)。
4. [递归反转链表的一部分](https://labuladong.gitbook.io/algo/mu-lu-ye-1/mu-lu-ye/di-gui-fan-zhuan-lian-biao-de-yi-bu-fen)。