天津市武清区住房建设网站,阿里云增加网站,代做ppt的网站,wordpress没小工具内容介绍 给你链表的头节点 head #xff0c;每 k 个节点一组进行翻转#xff0c;请你返回修改后的链表。 k 是一个正整数#xff0c;它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍#xff0c;那么请将最后剩余的节点保持原有顺序。 你不能只是单纯的改变节点内…内容介绍 给你链表的头节点 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]提示 链表中的节点数目为 n1 k n 50000 Node.val 1000 进阶你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗 完整代码 class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode hair new ListNode(0);hair.next head;ListNode pre hair;while (head ! null) {ListNode tail pre;// 查看剩余部分长度是否大于等于 kfor (int i 0; i k; i) {tail tail.next;if (tail null) {return hair.next;}}ListNode nex tail.next;ListNode[] reverse myReverse(head, tail);head reverse[0];tail reverse[1];// 把子链表重新接回原链表pre.next head;tail.next nex;pre tail;head tail.next;}return hair.next;}public ListNode[] myReverse(ListNode head, ListNode tail) {ListNode prev tail.next;ListNode p head;while (prev ! tail) {ListNode nex p.next;p.next prev;prev p;p nex;}return new ListNode[]{tail, head};}
}思路详解
一、解决思路
辅助头节点创建一个辅助头节点hair其下一个节点指向原链表的头节点head。这样做的好处是在翻转链表的过程中可以简化边界条件的处理。分组检查使用一个循环来检查链表中剩余的节点是否至少有 k 个以决定是否进行翻转。翻转链表对于每一组 k 个节点使用一个辅助函数myReverse来进行翻转。重新连接翻转后需要将翻转的子链表重新连接到原链表中。
二、详细步骤 初始化辅助头节点 ListNode hair new ListNode(0);
hair.next head;
ListNode pre hair;这里pre节点用于在翻转后重新连接链表。 遍历链表 while (head ! null) {当head不为空时继续处理链表。 检查剩余节点数量 ListNode tail pre;
for (int i 0; i k; i) {tail tail.next;if (tail null) {return hair.next;}
}通过一个循环检查从当前pre节点开始的 k 个节点是否存在。如果不足 k 个则直接返回辅助头节点的下一个节点。 记录翻转后的子链表 ListNode nex tail.next;
ListNode[] reverse myReverse(head, tail);
head reverse[0];
tail reverse[1];myReverse函数翻转从head到tail的子链表并返回翻转后的头尾节点。 重新连接链表 pre.next head;
tail.next nex;
pre tail;
head tail.next;将翻转后的子链表连接回原链表并更新pre和head指针。 翻转函数 public ListNode[] myReverse(ListNode head, ListNode tail) {ListNode prev tail.next;ListNode p head;while (prev ! tail) {ListNode nex p.next;p.next prev;prev p;p nex;}return new ListNode[]{tail, head};
}该函数通过迭代的方式翻转链表直到p指向tail。
四、返回结果
return hair.next;最终返回辅助头节点的下一个节点即翻转后的链表头节点。
通过以上步骤我们可以实现每 k 个一组翻转链表的功能。该算法的时间复杂度为 O(n)空间复杂度为 O(1)其中 n 是链表中的节点数量。
知识点精炼
一、链表基本概念
链表是由一系列节点组成的数据结构每个节点包含数据域和指针域。链表的第一个节点称为头节点最后一个节点的指针域为空。
二、K个一组翻转链表核心知识点
辅助头节点引入辅助头节点简化边界条件处理便于统一操作。分组检查通过循环检查链表剩余节点是否达到 k 个以决定是否进行翻转。链表翻转使用迭代方法实现链表翻转保持翻转过程中节点间的连接。重新连接翻转后的子链表需要重新连接到原链表中保持链表的完整性。
三、关键步骤
初始化创建辅助头节点初始化前驱节点pre。遍历与检查遍历链表检查每组是否有 k 个节点。翻转操作对每组 k 个节点进行翻转记录翻转后的头尾节点。连接链表将翻转后的子链表连接回原链表并更新前驱节点和当前节点。
四、注意事项
边界条件确保在节点数量不足 k 个时不进行翻转操作。指针更新在翻转和连接操作中正确更新指针避免链表断裂。辅助函数编写清晰的辅助函数简化主函数逻辑。
五、实际应用
链表操作掌握 K 个一组翻转链表提高链表操作能力。算法思维通过递归和迭代结合的方式培养灵活的算法思维。
