LeetCode - 反转链表 / K 个一组翻转链表

​欢迎光临小站：致橡树

​​​​​​反转链表

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 链表中节点的数目范围是 [0, 5000]

• -5000 <= Node.val <= 5000

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

解题思路

递归（尾插法）

递归递归，有递有归。

我们先「递」到链表的末尾节点，作为新链表的头节点。然后在「归」的过程中，一个一个地把节点插在新链表的末尾。

递归的基本思想

递归的核心在于将问题分解为更小的子问题，直到达到基本情况（base case），然后利用子问题的解构建原问题的解。

应用于链表反转

对于链表反转问题，我们可以这样思考：

• 基本情况：当链表为空或只有一个节点时，反转后的链表就是它本身。

• 递归步骤：假设我们已经能够反转除第一个节点外的剩余链表，然后只需要将第一个节点连接到已反转链表的末尾。

代码解析

public ListNode reverseList(ListNode head) {if (head == null) {return head; // 处理空链表的情况}return doReverseList(head); // 调用实际的递归函数
}public ListNode doReverseList(ListNode head) {// 基本情况：当前节点是最后一个节点if (head.next == null) {return head; // 返回这个节点作为新链表的头}// 递归反转剩余链表ListNode tail = doReverseList(head.next);// 关键操作：将当前节点连接到已反转链表的末尾ListNode newHead = head.next; // newHead实际上是原链表的下一个节点newHead.next = head;          // 将当前节点接在已反转链表的后面head.next = null;             // 断开原来的连接，防止循环return tail; // 返回新链表的头节点（即原链表的尾节点）
}

具体步骤说明

1. 终止条件：当head.next == null时，说明当前节点是最后一个节点，直接返回它作为新链表的头。

2. 递归调用：doReverseList(head.next)会反转从head.next开始的链表，并返回反转后的头节点（即原链表的尾节点）。

3. 连接当前节点：

   • newHead = head.next：获取已反转链表的最后一个节点（即原链表中当前节点的下一个节点）。

   • newHead.next = head：将当前节点接在已反转链表的后面。

   • head.next = null：断开当前节点与原链表的连接，防止循环。

4. 返回结果：最终返回的是原链表的尾节点，即反转后的新链表的头节点。

总结

这种递归解法简洁优雅，但需要注意：

1. 递归深度可能引发栈溢出（对于非常长的链表）。

2. 理解递归的关键在于信任递归函数能正确解决子问题，并专注于当前层的逻辑。

迭代（头插法）

核心思想

像翻书一样，每次只处理当前页（节点），把它的指向从后页改为前页，直到翻完全书（链表）。如果确实理解起来比较抽象，可以硬背下来，代码是比较固定的。

---

变量作用

1. prev：记录已反转部分的头节点（初始为null）

2. curr：当前待反转的节点（初始为head）

3. next：临时保存curr的下一个节点

---

四步操作流程

1. 备份后驱：next = curr.next
   （先记住下一个要处理的节点，避免断链后丢失）

2. 反转指针：curr.next = prev
   （将当前节点指向前一个节点，实现反转）

3. 移动prev：prev = curr
   （已反转部分的新头变成当前节点）

4. 移动curr：curr = next
   （继续处理下一个节点）

---

示例演示

初始状态：

null    [A] → [B] → [C] → null
pre     head

第1次循环：

1. next = B（记住B的位置）

2. A.next = null（A指向null）

3. pre = A（已反转部分：A→null）

4. head = B（准备处理B）

null ← [A]    [B] → [C] → nullpre    head

第2次循环：

1. next = C（记住C的位置）

2. B.next = A（B指向A）

3. pre = B（已反转部分：B→A→null）

4. head = C（准备处理C）

null ← [A] ← [B]    [C] → nullpre    head

第3次循环：

1. next = null（记住null位置）

2. C.next = B（C指向B）

3. pre = C（已反转部分：C→B→A→null）

4. head = null（处理完成）

null ← [A] ← [B] ← [C]

完整代码

class Solution {public ListNode reverseList(ListNode head) {ListNode pre = null;while(head!=null){ListNode next = head.next;head.next = pre;pre = head;head = next;}return pre;} 
}

K 个一组翻转链表

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

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

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

示例 1：

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

示例 2：

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

提示：

• 链表中的节点数目为 n

• 1 <= k <= n <= 5000

• 0 <= Node.val <= 1000

解题思路

1. 整体思路

   1. 特殊情况处理：如果k=1，不需要反转，直接返回原链表

   2. 创建虚拟头节点dummy：用于简化操作，最终返回dummy.next

   3. 遍历链表：每次处理一组K个节点

   4. 检查剩余节点是否足够K个：

      • 从当前head开始向后遍历k-1次

      • 如果中途遇到null，说明剩余节点不足k个

   5. 处理两种情况：

      • 如果剩余节点足够k个：反转这k个节点

      • 如果不足k个：保持这组节点顺序不变

   6. 将处理后的子链表连接到结果链表

   关键方法解析

   1. reverseKGroup方法

   • dummy节点：作为结果链表的虚拟头节点

   • cur指针：始终指向结果链表的末尾

   • 外层while循环：遍历原始链表

   • 内层while循环：检查剩余节点是否足够k个

   • flag标志：标记是否成功找到k个节点

   2. doReverse方法

   • 反转从head开始的k个节点

   • 使用迭代法反转：

     • 维护newHead作为反转后的头节点

     • 逐个节点反转指针方向

     • 每次处理一个节点，k减1

   代码执行流程示例

   以链表1→2→3→4→5，k=3为例：

   1. 第一组1→2→3：

      • 检查足够3个节点

      • 反转得到3→2→1

      • 连接到dummy后面

   2. 第二组4→5：

      • 检查发现只有2个节点(<k)

      • 不反转，直接连接到结果链表末尾

   最终结果：3→2→1→4→5

完整代码

class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode dummy = new ListNode(-1);ListNode cur = dummy;while (head != null) {ListNode start = head;int n = k;boolean flag = true;while (n > 0) {head = head.next;if (head == null) {flag = false;break;}n--;}while (cur.next != null) {cur = cur.next;}if (flag) {cur.next = doReverse(start, k);} else {cur.next = start;}}return dummy.next;}public ListNode doReverse(ListNode head, int k) {if (k == 1) {return head;}ListNode cur = head;ListNode newHead = null;while (k > 0 && cur != null) {ListNode next = cur.next;cur.next = newHead;newHead = cur;cur = next;k--;}return newHead;}public static void main(String[] args) {Solution solution = new Solution();ListNode head = new ListNode(1);head.next = new ListNode(2);head.next.next = new ListNode(3);head.next.next.next = new ListNode(4);head.next.next.next.next = new ListNode(5);ListNode listNode = solution.reverseKGroup(head, 5);System.out.println();}
}