leetcode热题HOT 25. K 个一组翻转链表

一、问题描述：

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

二、解题思路：

1. 使用递归的方式来实现链表按照长度为 k 的组进行反转。具体来说，在每次反转完一组长度为 k 的节点后，通过递归调用 reverseKGroup 方法处理剩余的链表部分，并将返回结果与已反转的部分连接起来。反转链表步骤参考第206题.反转链表。
2. 具体步骤：
   ①首先使用一个指针 len 来统计剩余的链表长度，用于判断是否至少还有一组长度为 k 的节点需要反转：
   （1）如果剩余长度小于 k，则说明无法组成一组，直接返回原链表头节点 head。
   （2）如果剩余长度大于等于 k，则进行一组长度为 k 的节点反转操作。
   ②定义两个指针 cur 和 pre，cur 指向当前要反转的节点，pre 用于连接已经反转的部分。
   ③使用循环进行 k 次反转操作，每次都执行以下步骤：
   （1）将 cur 的下一个节点保存到临时变量 temp 中。
   （2）将 cur 的 next 指针指向 pre，实现反转。
   （3）更新 pre 为当前反转后的节点，cur 为下一个待反转的节点。
   ④反转完成后，将反转后的部分与后面的链表递归连接起来。
   ⑤返回反转后的头节点 pre。

三、代码示例：

//时间复杂度为 O(n)
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 统计剩余长度
        ListNode len = head;
        for (int i = 0; i < k; ++i) {
            if (len == null) return head; // 如果剩余长度不足 k，则无法组成一组，直接返回原链表头节点
            len = len.next;
        }
        
        // 反转以 head 为头节点，长度为 k 的子链表
        ListNode cur = head, pre = null;
        int l = k;
        while (l-- > 0) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        
        // 反转后的部分连接后面的链表
        head.next = reverseKGroup(cur, k); // 递归处理剩下的链表并连接起来
        
        // 返回新的头节点
        return pre;
    }
}

• 时间复杂度分析：对于长度为 n 的链表，需要进行 n/k 组反转操作，每组反转需要 O(k) 的时间。因此，总体时间复杂度为 O(n)。