LeetCode 25 - K 个一组翻转链表

LeetCode 25 - K 个一组翻转链表

这道题是一个典型的链表操作题，考察我们对链表的精确操作，包括反转链表、分组处理、递归和迭代的结合应用等。还可以通过变体问题延伸到优先队列操作、归并、分块等，这使得它成为面试中的高频考题之一。

---

题目描述

给你一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。

• k 是一个正整数，它的值小于或等于链表的长度。
• 如果节点总数不是 k 的整数倍，那么请将最后剩余节点保持原样。
• 你不允许更改节点的值，只能调整节点指针的方向。

---

示例

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

---

解题思路与分析

核心简化问题

1. 分段处理链表：将链表分成每 k 个一组。
2. 对每一组执行反转操作。
3. 当遍历到不足 k 个节点的部分时，维持原顺序不再反转。
4. 方法可以通过递归或迭代完成。

---

解法与代码模板

解法 1：递归法

核心思路

• 使用递归配合局部反转：
  1. 确定链表是否有足够的 k 个节点：如果不足 k 个，直接返回头节点。
  2. 如果有足够的 k 个节点：
     • 完成当前组内 k 个节点的反转，
     • 递归地对剩余部分链表继续处理。
  3. 将当前反转的部分连接到下一组递归结果。

模板代码

class Solution {public ListNode reverseKGroup(ListNode head, int k) {// 检查链表是否有足够的 k 个节点ListNode current = head;int count = 0;while (current != null && count < k) {current = current.next;count++;}// 如果不足 k 个节点，直接返回原链表if (count < k) {return head;}// 反转当前 k 个节点ListNode prev = null, next = null;current = head;for (int i = 0; i < k; i++) {next = current.next;   // 暂存下一节点current.next = prev;  // 改变指针方向prev = current;       // 移动 prev 指针current = next;       // 移动 current 指针}// 递归处理剩余链表，并连接反转后的部分head.next = reverseKGroup(current, k);// 返回反转后的头节点return prev;}
}

复杂度分析

• 时间复杂度: O(N)
  • 每个节点仅访问一次。
• 空间复杂度: O(N / k)
  • 递归调用栈的深度为 (链表长度 / k)。

优缺点

• 优点:代码简洁并且逻辑清晰，适合递归思路的场景。
• 缺点:会造成大量递归栈调用，链表很长时可能出现栈溢出。

---

解法 2：迭代法

核心思路

• 相对于递归法，用 迭代 来实现分组反转链表，避免了递归栈空间的开销：
  1. 使用 哑结点（dummy node）作为新链表的起始位置，方便连接。
  2. 遍历链表，分别找到每一组的起始结点和结束结点。
  3. 将当前分组进行反转，并连接到已经处理好的链表部分。
  4. 当剩余节点不足时，停止反转，直接连接到尾部。

模板代码

class Solution {public ListNode reverseKGroup(ListNode head, int k) {// 创建哑结点ListNode dummy = new ListNode(-1);dummy.next = head;ListNode prevGroupEnd = dummy;while (true) {// 找到当前组的开始和结束节点ListNode groupStart = prevGroupEnd.next;ListNode groupEnd = prevGroupEnd;for (int i = 0; i < k; i++) {groupEnd = groupEnd.next;if (groupEnd == null) {return dummy.next; // 不足 k 个节点}}// 下一组的起始节点ListNode nextGroupStart = groupEnd.next;// 反转当前组reverseList(groupStart, groupEnd);// 连接反转后的部分prevGroupEnd.next = groupEnd; // 当前组的结尾变成起始点groupStart.next = nextGroupStart;// 更新 prevGroupEnd 为这一组的最后节点prevGroupEnd = groupStart;}}private void reverseList(ListNode start, ListNode end) {ListNode prev = null, current = start, next = null;ListNode stop = end.next; // 保存停止位置while (current != stop) {next = current.next;current.next = prev;prev = current;current = next;}}
}

复杂度分析

• 时间复杂度: O(N)
  • 每个节点最多被访问两次（反转和连接）。
• 空间复杂度: O(1)
  • 没有额外栈空间的使用，仅需常数级别指针。

优缺点

• 优点: 比递归方法更高效，适用于超长链表。
• 缺点: 实现逻辑上稍微复杂。

---

解法 3：栈辅助法

核心思路

• 借助栈来反转每一组节点：
  1. 遍历链表，将 k 个节点压入栈中。
  2. 当栈中节点数量达到 k 时，出栈并重新连接节点指针。
  3. 如果节点数量不足 k，直接连接剩余部分。

模板代码

import java.util.Stack;class Solution {public ListNode reverseKGroup(ListNode head, int k) {if (head == null || k <= 1) return head;Stack<ListNode> stack = new Stack<>();ListNode dummy = new ListNode(-1);ListNode prev = dummy;dummy.next = head;while (head != null) {// 将 k 个节点压入栈for (int i = 0; i < k && head != null; i++) {stack.push(head);head = head.next;}// 判断栈中是否有足够的 k 个节点if (stack.size() == k) {// 出栈并重新连接while (!stack.isEmpty()) {prev.next = stack.pop();prev = prev.next;}prev.next = head; // 连接当前组与下一组}}return dummy.next;}
}

复杂度分析

• 时间复杂度: O(N)
  • 每个节点入栈、出栈一次。
• 空间复杂度: O(k)
  • 栈空间用于存储每组 k 个节点。

优点和缺点

• 优点: 实现简单，不需要复杂链表反转逻辑。
• 缺点: 额外使用栈空间，适用于较短链表。

---

经典变体问题

变体 1：反转链表 II

• 反转链表的第 m 到第 n 个节点（LeetCode 92）。
• 解法类似，利用迭代进行指定区域反转。

---

变体 2：K 个一组翻转链表，但跳过一些组

• 例如：对链表分组，但只翻转奇数组或者仅反转偶数组。

---

变体 3：分组排序

• 例如：对链表的每组节点排序而不是反转。

---

快速 AC 总结

1. 递归与迭代优先掌握：
   • 递归：逻辑清晰但容易出现栈溢出，适用于理论验证。
   • 迭代：高效且空间复杂度较低，是面试中优选方法。
2. 哑节点技巧：
   • 在处理链表操作时，借助哑节点可以避免很多冗余的头节点边界条件处理。
3. 多练变体问题：
   • 如部分反转、跳过反转的场景，可以轻松迁移基础模板。

通过对链表反转操作的熟悉，配合经典模板化实现，可以快速应对链表转化类问题，并高效解决工程中复杂数据结构操作场景。