1.8 如何把链表以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）为了采用本章1.1节中链表翻转的算法，需要使end.next=null，在此之前需要记录下end指向的结点，用pNext来记录。

（3）使end.next=null，从而使得从begin到end为一个单独的子链表，可以对这个子链表采用1.1节介绍的方法进行翻转。

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

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

（6）把链表中剩余的还未完成翻转的子链表链接到已完成翻转的子链表后面（主要是针对剩余的结点的个数小于k的情况）。

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

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

接下来可以反复使用（1）～（8）这8个步骤对链表进行翻转。实现代码如下：

程序的运行结果为

运行结果分析：

由于k=3，因此，链表可以分成三组（1 2 3）、（4 5 6）、（7）。对（1 2 3）翻转后变为（3 2 1），对（4 5 6）翻转后变为（6 5 4），由于（7）这个子链表只有1个结点（小于3个），因此不进行翻转，所以翻转后的链表就变为：3->2->1->6->5->4->7。

算法性能分析：

这种方法只需要对链表进行一次遍历，因此，时间复杂度为O(n)。另外由于只需要几个指针变量来保存结点的地址信息，因此，空间复杂度为O(1)。