题目：反转链表
将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。
示例
初始代码
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode reverseKGroup (ListNode head, int k) {
// write code here
}
}
}
解法一
这道题是《反转链表》和《链表内指定区间反转》的进阶版。
（不清楚直接戳题目跳转哦~）
思路
我的整体思路和《链表内指定区间反转》基本一样，但是这一题是分组进行多次翻转，因此这一题多了分组的步骤，并且原来简单的处理“局部”翻转后的头尾问题变成了处理分组与分组之间的问题。
首先，还是处理特殊情况：
if (head == null || head.next == null || k <= 1) return head;
下面直接上图吧！
第一部分：
下面解决分组的问题：
在代码上就是这样实现滴：
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode reverseKGroup0 (ListNode head, int k) {
if (head == null || head.next == null || k == 1) return head;
int n = 1;
ListNode start = head;
ListNode cur = head;
ListNode curNext = cur.next;
while (n < k && curNext != null) {
cur = curNext;
curNext = curNext.next;
n++;
if (n == k) {
// 执行反转 和 分组间连接的问题……
reverse(start, cur);
start = curNext;
n = 0;
}
}
return head;
}
最后需要解决分组间的连接：
首先我们看反转后的“局部”是怎样的？
从上面的描述中可以看出，这里我们是以后一组为基准来调整，即：
后面一组反转之后，再将前一组的反转后的末尾和后一组反转后的头节点连接起来。
但是我们要注意每一组的start和end在反转前和反转后的改变。
反转后：原来是start变成了尾节点，原来的end编程了头结点，而start.next才是我们需要修改的。
对于第二组之后的组才存在前一组，因此这里我们需要判断这一次的反转是否为第一组的反转。
若非第一组，则将上一组的start.next置为这一组修改之前的end。
因此需要一个变量preStart用来保存上一组的start。
每一次反转，更新preStart的值。
并且第一组反转之前的end，在反转后即成为整个链表的头结点，因此可以在此时将head置为反转前的end。
代码标记：（截图方便标记，后面会有完整代码）
到这里整个题目就很清楚啦！
下面直接上代码~~
完整代码
/**
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode reverseKGroup0 (ListNode head, int k) {
if (head == null || head.next == null || k == 1) return head;
int n = 1;
ListNode start = head;
ListNode cur = head;
ListNode curNext = cur.next;
ListNode preStart = null;// 保存上一组的start
while (n < k && curNext != null) {
cur = curNext;
curNext = curNext.next;
n++;
if (n == k) {
if (start != head) {//不是第一组时
//前一组的start.next = 这一组的end（即cur）
preStart.next = cur;
}else {
// 是第一组，要把head设为cur，因为反转后cur就是头结点了
head = cur;
}
// 执行反转
preStart = start;// 更新preStart的值
reverse(start, cur);
start = curNext;
n = 0;
}
}
return head;
}
/*
反转，返回反转后的头
*/
private ListNode reverse(ListNode start, ListNode end) {
ListNode cur = start.next;
start.next = end.next;
while (cur != end) {
ListNode curNext = cur.next;
cur.next = start;
start = cur;
cur = curNext;
}
cur.next = start;
return end;//反转后的头
}
解法二
解法二是官方给的思路：递归。
虽然这并不符合题目空间复杂度O(1)的要求，但是我觉得思路还是很好的，而且代码写起来很简洁，所以这里也分享一下~
思路
下面结合代码就懂啦~
完整代码
/*
解法二：递归
时间复杂度：O(n)
*/
public ListNode reverseKGroup (ListNode head, int k) {
if (k <= 1) return head;
ListNode end = head;
for (int i = 1; i < k; i++) {
if (end == null || end.next == null) return head;
end = end.next;
}
// end 为待反转部分的尾部
// nextHead 为下一个待反转部分的头部
ListNode nextHead = end.next;
// 反转
reverse(head,end);
// 反转后 head 已经变为尾部，将尾部与下一组反转后的头部连接起来
head.next = reverseKGroup(nextHead, k);
return end;
// 是不是递归真的简单很多！！！！
}
/*
反转，返回反转后的头
*/
private ListNode reverse(ListNode start, ListNode end) {
ListNode cur = start.next;
// 这一句在这种解法中已经不需要 start.next = end.next;
while (cur != end) {
ListNode curNext = cur.next;
cur.next = start;
start = cur;
cur = curNext;
}
cur.next = start;
return end;//反转后的头
}```
关注我！一起加入每日一练吧！~
