搭建网站服务器教程,天津建设招标网站,网站建设找哪家,wordpress上传pdf文档LeetCode 25 - K 个一组翻转链表
这道题是一个典型的链表操作题#xff0c;考察我们对链表的精确操作#xff0c;包括反转链表、分组处理、递归和迭代的结合应用等。还可以通过变体问题延伸到优先队列操作、归并、分块等#xff0c;这使得它成为面试中的高频考题之一。 题目…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]解题思路与分析
核心简化问题
分段处理链表将链表分成每 k 个一组。对每一组执行反转操作。当遍历到不足 k 个节点的部分时维持原顺序不再反转。方法可以通过递归或迭代完成。 解法与代码模板
解法 1递归法
核心思路
使用递归配合局部反转 确定链表是否有足够的 k 个节点如果不足 k 个直接返回头节点。如果有足够的 k 个节点 完成当前组内 k 个节点的反转递归地对剩余部分链表继续处理。 将当前反转的部分连接到下一组递归结果。
模板代码
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迭代法
核心思路
相对于递归法用 迭代 来实现分组反转链表避免了递归栈空间的开销 使用 哑结点dummy node作为新链表的起始位置方便连接。遍历链表分别找到每一组的起始结点和结束结点。将当前分组进行反转并连接到已经处理好的链表部分。当剩余节点不足时停止反转直接连接到尾部。
模板代码
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栈辅助法
核心思路
借助栈来反转每一组节点 遍历链表将 k 个节点压入栈中。当栈中节点数量达到 k 时出栈并重新连接节点指针。如果节点数量不足 k直接连接剩余部分。
模板代码
import java.util.Stack;class Solution {public ListNode reverseKGroup(ListNode head, int k) {if (head null || k 1) return head;StackListNode 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。解法类似利用迭代进行指定区域反转。 变体 2K 个一组翻转链表但跳过一些组
例如对链表分组但只翻转奇数组或者仅反转偶数组。 变体 3分组排序
例如对链表的每组节点排序而不是反转。 快速 AC 总结
递归与迭代优先掌握 递归逻辑清晰但容易出现栈溢出适用于理论验证。迭代高效且空间复杂度较低是面试中优选方法。 哑节点技巧 在处理链表操作时借助哑节点可以避免很多冗余的头节点边界条件处理。 多练变体问题 如部分反转、跳过反转的场景可以轻松迁移基础模板。
通过对链表反转操作的熟悉配合经典模板化实现可以快速应对链表转化类问题并高效解决工程中复杂数据结构操作场景。
