一、题目
给你链表的头节点 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]
提示：
- 链表中的节点数目为
n 1 <= k <= n <= 50000 <= Node.val <= 1000
二、解题思路
1. 创建一个虚拟头节点 dummy，它的 next 指向原链表的头节点 head。这样可以在反转链表时不影响原链表的头节点。
2. 创建一个指针 prev 用于跟踪当前要反转的子链表的前一个节点，初始化为 dummy。
3. 创建一个指针 current 用于遍历链表，初始化为 head。
4. 使用一个循环来处理每个长度为 k 的子链表，直到 current 到达链表末尾或无法组成完整的 k 个节点的子链表：
- 在每次循环开始时，检查是否有足够的节点来反转（即
current至少向前k个节点）。 - 如果有足够的节点，开始反转
k个节点：- 初始化三个指针
next，newHead和tail，next用于临时存储下一个节点，newHead用于指向新反转的子链表的头节点，tail用于指向当前子链表的最后一个节点。 - 在反转过程中，不断更新这三个指针的值，直到反转完成。
- 初始化三个指针
- 更新
prev.next指向新反转的子链表的头节点，prev指向当前子链表的尾节点，current指向下一组的头节点（如果有的话）。
5. 返回虚拟头节点的 next，即反转后的链表的头节点。
三、具体代码
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k == 1) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
ListNode current = head;
ListNode next;
while (current != null && current.next != null) {
// 检查是否有足够的节点来反转
next = current;
for (int i = 0; i < k; i++) {
if (next == null) {
break;
}
next = next.next;
}
if (next == null) {
break;
}
// 反转k个节点
ListNode newHead = prev.next;
ListNode tail = current;
for (int i = 0; i < k; i++) {
next = current.next;
current.next = newHead;
newHead = current;
current = next;
}
prev.next = newHead;
tail.next = current; // 连接反转后的子链表的尾节点到下一组的头节点
prev = tail; // 更新prev指针
}
return dummy.next;
}
}四、时间复杂度和空间复杂度
1. 时间复杂度
- 外层循环遍历链表中的每个节点，对于每个节点，内层循环最多执行 k 次（尝试找到 k 个连续的节点）。
- 内层循环中的操作是常数时间操作，因此内层循环的时间复杂度是 O(k)。
- 外层循环的时间复杂度是 O(n)，其中 n 是链表的总节点数。
- 综合起来，总的时间复杂度是 O(kn)，这是因为每个节点最多被访问两次（一次在外层循环中，一次在内层循环中）。
2. 空间复杂度
- 代码中使用了常数数量的额外空间来存储指针（
dummy,prev,current,next,newHead,tail）。 - 所有这些指针都是独立的，不依赖于输入链表的大小。
- 因此，空间复杂度是 O(1)，即常数空间复杂度。
五、总结知识点
1. 虚拟头节点（Dummy Head）：
- 创建一个虚拟头节点
dummy，它的next指向原链表的头节点head。这是一种常用的技巧，用于简化边界条件，特别是在处理链表的头节点时。
2. 链表遍历和反转：
- 使用一个
while循环来遍历链表，寻找长度为 k 的子链表。 - 在找到的子链表中，使用三个指针（
prev、current和next）来辅助完成反转操作。 - 反转过程中，通过改变节点的
next指针方向来实现链表的反转。
3. 指针操作：
- 在反转过程中，
prev指针始终指向当前子链表的前一个节点。 current指针用于遍历链表，找到需要反转的节点。next指针临时存储下一个节点，以便在反转过程中更新current.next。
4. 条件检查：
- 在每次尝试反转之前，代码检查是否有足够的节点来形成一个长度为 k 的子链表。如果不足 k 个节点，则跳出循环，不再进行反转。
5. 连接反转后的子链表：
- 反转完成后，将反转后的子链表的头节点（
newHead）连接到前一个子链表的尾节点（prev）。 - 同时，更新
tail指针（原子链表的尾节点）的next指针，使其指向下一个子链表的头节点（如果有的话）。
6. 返回结果：
- 最后，返回虚拟头节点的
next指针，即反转后链表的新头节点。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。
