描述

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表 如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样 你不能更改节点中的值，只能更改节点本身。

数据范围：2000 0≤n≤2000 ， 1≤k≤2000 ，链表中每个元素都满足 10000≤val≤1000 要求空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

例如：

给定的链表是 1→2→3→4→5

对于 k = 2k=2 , 你应该返回 2→1→4→3→5

对于 k = 3k=3 , 你应该返回 3→2→1→4→5

题目分析

我们可以将前k个长度的链表作为一个单独的链表，然后将之后的链表作为一个链表，这样我们便可以先翻转前k个长度的链表，然后再翻转后面的链表，最后将这两个链表连接起来，这么一看，后面的链表依旧在重复着链表的链表的翻转过程，因此可以使用递归的方式来翻转链表

代码实现

每k个长度的节点当做一个独立的链表，这样，我们便可以使用双指针的形式翻转这个独立的链表，然后将新的链表连接起来就行

/*
 * 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) {
        // 不需要翻转的条件
        if (head == null || k <= 1) {
            return head;
        }
        ListNode kNode = head;
        // 找到kNode
        for (int i = 0; i < k - 1; i++) {
            kNode = kNode.next;
            // 链表长度不足k，不翻转
            if(kNode == null) {
                return head;
            }
        }
        // 剩下链表的头结点
        ListNode nextHead = kNode.next;
        // 断开链表，将前k个链表变成独立的链表
        kNode.next = null;
        // 翻转链表的薪的头节点
        ListNode newHead = reverse(head);
        // 此时的head变成了k链表的tail，reverseKGroup返回的是剩余链表翻转后的头节点，
        // 将尾节点和剩余链表返回的头结点连接起来，则构成了新的链表
        head.next = reverseKGroup(nextHead, k);
        // 返回新链表的头节点
        return newHead;
    }
    
    /**
    * 翻转单个链表
    */
    public ListNode reverse(ListNode head) {
        if(head == null) {
            return head;
        }
        // 采用双指针翻转链表
        ListNode prev = head;
        ListNode current = head.next;
        // 断开head和next，防止形成环
        head.next = null;
        while(current != null) {
            // 获取下一个node
            ListNode next = current.next;
            // 将current的next指向prev，进行链表翻转
            current.next = prev;
            // 移动双指针
            prev = current;
            current = next;
        }
        // 此时current指向null，prev变成翻转链表的head
        return prev;
    }
    
}

算法需要练习才能掌握精髓，附上算法练习地址，有需要的小伙伴可以上去练习一下

链表中的节点每k个一组翻转_牛客题霸_牛客网

注：牛客网上的算法题按照专题分类，更适合突击训练使用