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

Nen 2022-03-24 16:51

- 程序员

主要思路为：首先把前k个结点看成一个子链表，采用前面介绍的方法进行翻转，把翻转后的子链表链接到头结点后面，然后把接下来的k个结点看成另外一个单独的链表进行翻转，把翻转后的子链表链接到上一个已经完成翻转子链表的后面。具体实现方法如图9-4所示。

图9-4 链表旋转方法

在图9-4中，以k=3为例介绍具体实现的方法。

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

2）为了采用9.1节中链表翻转的算法，需要使end.next=None，在此之前需要记录下end指向的结点，用pNext来记录。

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

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

5）由于翻转后子链表的第一个结点从begin变为end，因此，执行pre.next=end，把翻转后的子链表链接起来。6）把链表中剩余的还未完成翻转的子链表链接到已完成翻转的子链表后面（主要是针对剩余的结点的个数小于k的情况）。

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

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

程序的运行结果为：

运行结果分析：由于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)。

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

最佳答案 2022-03-25 17:15

轩辕小不懂的其他提问

类似问题

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

最佳答案 2022-03-25 17:15

轩辕小不懂 的其他提问

类似问题

轩辕小不懂的其他提问