题目： K 个一组翻转链表

题目

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明：

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

思路

在翻转链表的时候，可以借助三个指针：prev、curr、next，分别代表前一个节点、当前节点和下一个节点，实现过程如下所示。

1. 将 curr 指向的下一节点保存到 next 指针；
2. curr 下一个指向 prev，prev和curr一起前进一步；
3. 重复之前步骤，直到 k 个元素翻转完毕；
4. 当完成了局部的翻转后，prev 就是最终的新的链表头，curr 指向了下一个要被处理的局部，而原来的头指针 head 成为了链表的尾巴。
   

代码

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 头判空、是否够k个
        if (head == null) {
            return null;
        }
        ListNode p = head;
        for (int i = 0; i < k; i++) {
            if (i >= k - 1) {
                break;
            }
            if (p.next != null) {
                // 每循环一次p移动，到尾后判断是否够k
                p = p.next;
            } else if (i < k - 1) {
                // 不够直接返回
                return head;
            }
        }

        // k个翻转
        ListNode prev, curr, next;
        curr = head;
        prev = null;
        for (int i = 0; i < k; i++) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        // 递归翻转其它局部
        head.next = reverseKGroup(curr, k);
        // 此时prev指向第k个，curr指向下一组第一个
        return prev;
    }
}

class ListNode {
    int val;
    ListNode next;

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