当前位置：首页 > news >正文

如何高效实现「LeetCode25. K 个一组翻转链表」？Java 详细解决方案

news 2025/5/11 8:24:56

文章目录

- - - 问题描述
    - 核心思路
    - 详细实现步骤
    - - 1. 初始化虚拟头节点
      - 2. 指针定位分组
      - 3. 分组翻转逻辑
      - 4. 翻转函数 `reverse()`
    - 完整代码实现
    - 代码解析
    - 复杂度分析
    - 示例演示
    - 总结

问题描述

LeetCode 25. K 个一组翻转链表
给定一个链表的头节点 head 和一个整数 k，要求每 k 个节点一组进行翻转。如果剩余节点不足 k 个，则保持原有顺序。返回翻转后的链表头节点。

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

核心思路

分组处理：将链表按 k 个节点分组，每组内部翻转。
虚拟头节点：引入虚拟头节点简化边界处理（如原头节点被翻转的情况）。
指针定位：使用两个指针 pre 和 end 定位每组的前驱节点和末尾节点。
断链与连接：翻转后需正确连接前一组尾节点与当前组头节点，以及当前组尾节点与下一组头节点。

详细实现步骤

1. 初始化虚拟头节点

创建 dummy 节点，指向原链表头节点，避免处理头节点翻转的特殊情况。

2. 指针定位分组

pre：始终指向当前待翻转分组的前驱节点。
end：遍历链表，定位当前分组的末尾节点。

3. 分组翻转逻辑

移动 end 指针：向后移动 k 次找到当前分组的末尾。
断链：将当前分组与后续节点断开。
翻转当前分组：调用 reverse() 函数翻转当前分组。
重新连接：将翻转后的头节点连接到前驱节点，翻转后的尾节点连接到下一组头节点。
更新指针：将 pre 和 end 移动到下一组的前驱节点位置。

4. 翻转函数 `reverse()`

使用迭代法翻转链表，返回新头节点。

完整代码实现

class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode pre = dummy; // 当前组的前驱节点ListNode end = dummy; // 当前组的末尾节点while (end.next != null) {// 1. 定位当前组的末尾for (int i = 0; i < k && end != null; i++) {end = end.next;}if (end == null) break; // 剩余节点不足k个，直接结束// 2. 断链并翻转ListNode start = pre.next; // 当前组的起始节点ListNode nextGroup = end.next; // 下一组的头节点end.next = null; // 断开当前组与后续节点的连接// 3. 翻转当前组，并重新连接链表pre.next = reverse(start); // 翻转后的头节点连接到前驱start.next = nextGroup; // 原组的头（翻转后的尾）连接到下一组// 4. 移动pre和end到下一组的前驱位置pre = start;end = pre;}return dummy.next;}// 迭代法翻转链表private ListNode reverse(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;}
}

代码解析

虚拟头节点 dummy
- 作用：避免处理头节点被翻转的特殊情况。
- 初始化 dummy.next = head，最终返回 dummy.next。
指针移动与分组定位
- end 指针移动 k 步找到当前组的末尾。若中途遇到 null，说明剩余节点不足 k 个，直接结束循环。
断链与翻转
- 保存当前组的起始节点 start 和下一组的头节点 nextGroup。
- 断开当前组与后续节点的连接：end.next = null。
- 调用 reverse(start) 翻转当前组，并将翻转后的头节点连接到前驱节点 pre。
重新连接链表
- 翻转后的尾节点（原 start）需要连接到下一组的头节点：start.next = nextGroup。
- 更新 pre 和 end 到下一组的前驱位置（即原 start 的位置）。