25.K 组触发器
最编程
2024-10-09 07:09:48
...
目录
一、问题描述
二、解题思路
三、代码
四、复杂度分析
一、问题描述
给你链表的头节点 head
,每 k
个节点一组进行翻转,请你返回修改后的链表。
k
是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k
的整数倍,那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。
二、解题思路
这道题要求我们每隔 k
个节点将其翻转,涉及到链表的操作。主要的思路是逐步遍历链表,当到达 k
个节点时进行翻转,否则保持剩余节点的顺序。
主要步骤如下:
-
确定链表段落:
我们首先遍历链表以确定链表是否有足够的k
个节点,如果不足k
个节点,就不需要翻转这些节点。 -
翻转 k 个节点:
对于每段k
个节点,我们要进行翻转。翻转过程中,我们需要重新连接前后段的节点,同时保证翻转后链表的顺序正确。 -
递归/迭代处理:
在处理完一组k
个节点之后,继续对后面的节点重复这个过程,直到所有节点都处理完毕。如果剩余的节点不足k
,则保持原顺序。 -
边界条件:
如果链表为空,或k
为 1,那么链表无需做任何变动,直接返回即可。
三、代码
class Solution {
// 主函数:接收链表头节点head和整数k,返回每k个节点翻转后的链表
public ListNode reverseKGroup(ListNode head, int k) {
// 创建一个虚拟头节点,dummy.next指向head,这样可以处理头节点的变化
ListNode dummy = new ListNode(0);
dummy.next = head;
// prev指向需要翻转的k个节点的前一个节点,end用于找到每一组k节点的末尾
ListNode prev = dummy;
ListNode end = dummy;
while (true) {
// 将end指针向前移动k步,找到需要翻转的k个节点的结尾
for (int i = 0; i < k && end != null; i++) {
end = end.next;
}
// 如果剩余的节点不足k个,则直接返回结果,不进行翻转
if (end == null) break;
// 开始翻转当前这k个节点
ListNode start = prev.next; // 记录当前k组的第一个节点
ListNode next = end.next; // 记录下一个需要处理的节点
end.next = null; // 切断当前k组和后面节点的连接
// 翻转这k个节点,并且返回翻转后的头节点
prev.next = reverse(start);
// 将翻转后的k组与下一个部分连接
start.next = next;
// 更新prev和end指针,准备处理下一组
prev = start;
end = prev;
}
// 返回最终处理后的链表
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指针
prev = curr;
curr = next;
}
// 返回翻转后的新头节点
return prev;
}
}
四、复杂度分析
时间复杂度:
- 每次遍历 k 个节点,然后翻转 k 个节点,时间复杂度为 O(n),其中 n 是链表的节点总数。
空间复杂度:
- 除了使用常数级别的额外空间 (dummy 节点, 指针等),空间复杂度为 O(1)。