K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group

image.png
image.png
就拿示例2来分析：
1.先把整个链表拆解成两份：
image.png
第一组是满足k（k=3）个节点的，可以进行翻转。
第二组无法满足k（k=3）个节点，不可进行翻转。

眼前的问题就是如何判断分解后的各组链表是否满足翻转条件？

最简单直接的办法就是遍历链表。

• 条件1:满足翻转条件的链表只需要遍历k次就结束遍历
• 条件2:不满足条件的链表next节点为null，导致无法达到k次遍历

ListNode next = head;
// 统计遍历的节点数量，用来检测是否满足k个节点的要求
int count = 0;
// 循环遍历链表，直至满足k个阶段，或者next指针为null就结束遍历
while (count < k && next != null){
    next = next.next;
    count++;
}
// 如果满足要求，就执行翻转
if (count == k){
// 执行翻转  TODO

} else {
// 不满足要求，那么返回链表本身，不需要翻转
    return head;
}

2.链表翻转

image.png

• 翻转前，需要提前把下一个节点暂存起来，这样才能遍历下去，所以需要准备好ListNode next变量。
• 另外还需要准备ListNode prev，这个是用来作为翻转指针的指向目标

// 保留原来的head指针，创建一个临时指针来翻转。不改变head指向。
ListNode current = head;
ListNode next = null;
ListNode prev = null;
while (循环条件) {
    // 暂存next节点。对应上图第一阶段
    next = current.next;
    // 反转current节点的next指针。对应上图第二阶段
    current.next = prev;
    // 翻转后处理，移动prev、current指针。对应上图第三阶段
    prev = current;
    current = next;
}

如此往复循环，直至翻转的次数达到k次，或者current节点为null，那么就结束循环
循环条件：

• 翻转次数达到k次
• current节点为null

ListNode current = head;
ListNode next = null;
ListNode prev = null;
int count = 0;
while (count < k && current != null) {
    next = current.next;
    current.next = prev;
    prev = current;
    current = next;
    count++;
}

3.翻转完毕后，会存在以下两种情况

image.png

• next不为null的话，那么就需要把next指向的链表再次执行翻转。

  
  image.png
• next为null，后续不需要做任何处理，直接返回prev节点

if (next !=null){
    head.next = k个节点链表翻转
}
return prev;

最终代码：

public ListNode reverseKGroup(ListNode head, int k){
    // 首先，判断链表是否满足k个节点
    // 需要遍历链表
    ListNode next = head; 
    int count = 0;
    // 遍历链表，统计数量
    while (count < k && next != null){
        next = next.next;
        count++;
    }
    // 检查是否是否满足k
    if (count == k){
        // 执行翻转操作
        ListNode prev = null;
        next = null;
        // 临时指针
        ListNode current = head;
        // 计算翻转次数
        count = 0;
        while (count < k && current != null){
            // 暂存next节点
            next = current.next;
            // 翻转指向
            current.next = prev;
            // 翻转后指针向后移动
            prev = current;
            current = next;
        }
        if (next != null){
            // 如果翻转后next不为null，说明后面的链表同样需要翻转
            head.next = reverseKGroup(next, k);
        }
        // 返回翻转后的链表头节点
        return prev;
    } else {
        // 不满足k个节点，直接返回原链表head
        return head;
    }
}