K 个一组翻转链表

给你链表的头节点 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]

在解决上述问题时，需要先了解一组链表的反转

一组链表反转

链表节点结构

public class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

解决方法：

        一组链表反转从左往右依次更改当前的next节点为上一个，需要用一个临时节点存储当前节点的next节点，避免更改后找不到这个节点

        在更改为上一个后，将pre节点设置为当前节点，cur设置为临时节点，临时节点在每次循环时赋值为cur节点的next节点

根据上述方法的描述，写出下列代码

// 反转链表  
ListNode reverse(ListNode head) {  // pre指针用于记录当前节点的前一个节点，初始化为null  // cur指针用于遍历链表  ListNode pre = null;  ListNode cur = head;  // 当cur不为空时，继续反转  while(cur != null) {  // 保存cur的下一个节点  ListNode tmp = cur.next;  // 反转当前节点的指向  cur.next = pre;  // 移动pre和cur指针  pre = cur;  cur = tmp;  }  // 返回反转后的链表的头节点（原链表的尾节点）  return pre;  
}

在了解一组链表的反转后再看k个一组链表反转

k个一组链表反转

解决方法：

方法一：反转既是先进后出的特点，使用栈来解决，栈中包含k个值的时候，依次弹出

方法二：分成多个一组链表反转，可以在空间复杂度为O(1)的情况下完成反转

        初始需要两个变量 pre 和 cur，pre 代表待翻转链表的前驱节点，cur代表待翻转链表的末尾节点

        经过k次循环，cur到达本次反转的末尾，记录待翻转链表的后继

        使用两个遍历start和end，start代表待翻转链表的初始节点，end代表待翻转链表的后驱节点

        cur的下一个节点设置为null，避免影响后续节点顺序，在对start节点进行反转，并返回反转后的头节点赋值给pre的下一个节点，start此时是反转后的末尾节点，设置下一个为end

        将cur设置成end节点，pre设置成start节点

        

时间复杂度为 O(n∗K) 最好的情况为 O(n) 最差的情况未 O(n^2)

空间复杂度为 O(1) 除了几个必须的节点指针外，我们并没有占用其他空间

使用方法二来解决这个问题

 方法二对应的代码如下

public ListNode reverseKGroup(ListNode head, int k) {  // 创建一个哑节点(dummy node)，它的next指向链表的头节点  // 哑节点的作用是方便处理头节点被反转的情况  ListNode dum = new ListNode(0);  dum.next = head;  // pre指针用于记录每组反转链表的前一个节点  // cur指针用于遍历链表  ListNode pre = dum;  ListNode cur = dum;  // 当cur指针的下一个节点不为空时，继续遍历  while(cur.next != null) {  // 向前移动cur指针k步，检查接下来的k个节点是否存在  for(int i = 0; i < k && cur != null; i++) cur = cur.next;  // 如果cur为空，说明剩余节点不足k个，跳出循环  if (cur == null) break;  // 记录每组需要反转的链表的起始节点和结束节点的下一个节点  ListNode start = pre.next;  ListNode end = cur.next;  // 将cur的next置为null，切断与后续节点的连接，准备反转  cur.next = null;  // 反转start到end之间的链表，并更新pre.next指向反转后的链表头  pre.next = reverse(start);  // 将反转后的链表的尾节点指向原链表中下一组的头节点  start.next = end;  // 更新pre和cur指针，pre指向反转后的链表的尾节点，cur也指向这里  // 以便下一轮循环从新的位置开始  pre = start;  cur = start;  }  // 返回反转后的链表的头节点（哑节点的下一个节点）  return dum.next;  
}  // 反转链表  
ListNode reverse(ListNode head) {  // pre指针用于记录当前节点的前一个节点，初始化为null  // cur指针用于遍历链表  ListNode pre = null;  ListNode cur = head;  // 当cur不为空时，继续反转  while(cur != null) {  // 保存cur的下一个节点  ListNode tmp = cur.next;  // 反转当前节点的指向  cur.next = pre;  // 移动pre和cur指针  pre = cur;  cur = tmp;  }  // 返回反转后的链表的头节点（原链表的尾节点）  return pre;  
}

 至此题目完成