如何把链表以K个结点为一组进行翻转

题目描述：

K链表翻转是指把每K个相邻的结点看成一组进行翻转，如果剩余结点不足K个，则保持不变。假设给定链表1->2->3->4->5->6->7和一个数K，如果K的值为2，那么翻转后的链表2->1->4->3->6->5->7。如果K的值为3，那么翻转后的链表为3->2->1->6->5->4->7。

分析：

主要思路是首先把前K个结点看成一个子链表，采用前面的方法进行翻转，把翻转后的子链表链接到头结点后面，然后把接下来的K个结点看成另外一个单独的链表进行翻转，把翻转后的子链表链接到上一个已经完成翻转的子链表后面。如下图所示：

在上图中，以K=3为例

1、首先设置pre指向头结点，然后让begin指向链表的第一个结点，找到从begin开始的第K=3个结点end。

2、为了将链表进行翻转，需要end.next=null，在此之前需要记录下end指向的节点，用pNext记录。

3、使end.next=null，使得从begin到end为一个单独的子链表，从而可以对这个子链表进行翻转。

4、对以begin为第一个结点，end为尾结点所对应的K=3的结点进行翻转。

5、由于翻转后的子链表的第一个结点从begin变成end，因此执行pre.next=end，把翻转后的子链表链接起来。

6、把链表中剩余的还未完成翻转的子链表链接到已完成翻转的子链表后面

7、让pre指针指向已完成翻转的链表的最后一个结点。

8、让begin指针指向下一个需要翻转的子链表的第一个结点（通过begin=pNext实现）

代码如下

public static Node reverseKGroup(Node head, int k) {
        Node dummy = new Node(0);
        dummy.next = head;

        Node pre = dummy;
        Node end = dummy;

        while (end.next != null) {
            for (int i = 0; i < k && end != null; i++) end = end.next;
            if (end == null) break;
            Node start = pre.next;
            Node next = end.next;
            end.next = null;
            pre.next = reverse(start);
            start.next = next;
            pre = start;

            end = pre;
        }
        return dummy.next;
    }

    private static Node reverse(Node head) {
        Node pre = null;
        Node curr = head;
        while (curr != null) {
            Node next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

算法性能分析：

时间复杂度为O(N)，空间复杂度为O（1）