25.K 个一组翻转链表
难度困难416
给你一个链表，每 *k *个节点一组进行翻转，请你返回翻转后的链表。
*k *是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 *k *的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：1->2->3->4->5
当 *k *= 2 时，应当返回: 2->1->4->3->5
当 *k *= 3 时，应当返回: 3->2->1->4->5
说明：
- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
/***
* 迭代法
* 1.链表分区已翻转 + 待翻转 + 未翻转部分
* 2.翻转前确定翻转的范围 通过k来决定
* 3.记录链表前驱和后继 方便翻转完成后，把已翻转和未翻转连接起来。
* 4.初始化两个边路pre end pre >代表待翻转链表的前驱，end代表待翻转的末尾。
* 5.经过k次 end到达链表末尾。 记录待翻转链表的后继 next = end.next
* 6.翻转链表，将三部分连接起来，然后重置pre 和 end 指针 进入下一个循环
* 7.特殊情况 翻转部分长度不足k时，在定位end 完成后，end = null 已经到达末尾。
* 8.时间复杂度为 O(n*K) 最好的情况为 O(n) 最差的情况未 O(n^2)
* 9.空间复杂度为 O(1)
* @param head
* @param k
* @return
*/
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dumy = new ListNode(0);
dumy.next = head;
ListNode pre = dumy;
ListNode end = dumy;
while (end.next != null) {
//确定待翻转的范围
for (int i = 0; i < k && end != null; i++) {
end = end.next;
}
if (end == null) {
break;
}
ListNode start = pre.next;//待翻转链表的开始位置
ListNode next = end.next;//下一个待翻转链表的起始位置
end.next = null;//和后继待翻转链表断开
pre.next = reverse(start);
start.next = next;
pre = start;
end = pre;
}
return dumy.next;
}
public static ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode curr = head;
//假设 1 -> 2 -> 3
while (curr != null) {
ListNode next = curr.next; // next = 2 // next = 3
curr.next = pre;// 1.next = null // 3.next = 1
pre = curr;// pre = 1; // 1 = 3
curr = next; // curr = 2 // 3 = null
}
return pre; //
}