No.25 K个一组翻转链表 （Hard）

题目描述

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。

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

进阶：

你可以设计一个只使用常数额外空间的算法来解决此问题吗？
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例：k = 2

示例2：k = 3

思路

该题为No.24的加强版，No.24仅仅反转2个结点，这里是反转k个结点，仍然可以通过递归的方式来解决。

1. 用head指向k个一组结点中的第一个结点，用tail指向k个一组结点中的最后一个结点的下一个结点，例如：

在示例2中，head指向1， tail指向4（而不是3）。

1. 翻转[head, tail)中的结点，注意是左闭右开区间，即反转1,2,3并返回结点3作为新的头结点newHead
2. newHead指向下一次递归翻译的另一个newHead，形成递归

代码

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // head == null 表示最后没有结点了
        // head.next == null 表示最后仅剩一个结点，不需要反转了
        if (head == null || head.next == null) {
            return head;
        }
        ListNode tail = head;
        // 找到tail位置，例如在示例2中，tail指向4
        for (int i = 0; i < k; i++) {
            // 如果tail == null 表示结点数量少于k个，不进行反转，直接返回头结点即可
            // 提前判断tail == null还有个好处，就是可以避免tail = tail.next代码出现空指针
            if (tail == null) {
                return head;
            }
            tail = tail.next;
        }
        // 反转1->2->3，并返回3， 此时newHead指向3，链表变成了3->2->1
        ListNode newHead = reverse(head,tail);
        // head指向下一组反转完成后的结点的头结点,这里head是1
        // 注意不是newHead = reverseKGroup(tail, k);
        // 因为java是值传递，所以这里的head与传进reverse里的head不是同一个引用
        // 也就是说，虽然在reverse方法里改变了head的指向，但是并未改变外部head的指向，head仍然指向1
        head.next = reverseKGroup(tail, k);
        // 返回反转完成的头结点。
        return newHead;
    }
    // 该方法反转head到tail之间的结点，注意是左闭右开
    private ListNode reverse(ListNode head, ListNode tail) {
        ListNode pre = null;
        ListNode nextNode = null;
        // 每次循环反转2个结点，pre和head
        // 当head == tail 时，表示反转结束了
        while (head != tail) {
            // 用nextNode保存head的下一个结点，为了在改变指向后，最终让head = nextNode
            nextNode = head.next;
            head.next = pre;
            pre = head;
            head = nextNode;
        }
        // 最终head和tail都指向下一组结点的开头，pre指向完成反转后的新的头结点
        return pre;
    }
}