1.8 如何把链表以k个结点为一组进行反转

【出自MT笔试题】

难度系数：★★★☆☆　被考察系数：★★★★☆

题目描述：

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开始第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）对链表进行反转。

实现代码如下：

程序的运行结果为

运行结果分析：

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

算法性能分析：

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