2.3 链表的分组算法设计

2.3.1 LeetCode92——反转链表Ⅱ★★

【问题描述】 给定单链表head以及两个整数left和right，其中left≤right，反转从位置left到位置right的链表结点，返回反转后的链表。

例如，head=[1，2，3，4，5]，left=2，right=4，反转后head=[1，4，3，2，5]，如图2.20所示。

【限制】 链表中结点的数目为 n ，1≤ n ≤500，-500≤Node.val≤500，1≤left≤right≤ n 。

【解题思路】 整个链表作为一组 + 用头插法建表 。先为单链表head添加一个头结点h，通过遍历找到left位置的结点p，pre指向其前驱结点，用q遍历位置left+1～right的结点，通过结点p删除结点q，并将结点q链接到pre之后，如图2.21所示。

对应的算法如下。

C++：

提交运行：

Python：

提交运行：

2.3.2 LeetCode24——两两交换链表中的结点★★

【问题描述】 给定一个链表head，两两交换其中相邻的结点，并返回交换后链表的首结点。要求在不修改结点内部的值的情况下完成本题，即只能进行结点的交换。

例如，head=[1，2，3，4，5]，两两交换后的链表head=[2，1，4，3，5]，如图2.22所示。

【限制】 链表中结点的数目在[0，100]范围内，0≤Node.val≤100。

【解题思路】 两个相邻结点作为一组+用尾插法建表。先创建一个空结果单链表h，用p和p- next遍历两个相邻的结点，若存在这样的两个结点，置a=p，b=p- next，p=b- next，然后依次将b和a结点链接到链表h的末尾，如图2.23所示，再对p和p- next做同样的处理。当只剩余结点p时将结点p链接到链表h的末尾。最后将尾结点r的next域置为空，返回h- next即可。

对应的算法如下。

C++：

提交运行：

Python：

提交运行：

2.3.3 LeetCode25—— k 个一组翻转链表★★★

【问题描述】 给定一个单链表head，将每 k 个结点作为一组进行翻转，返回修改后的链表。其中 k 是一个正整数，它的值小于或等于链表的长度。如果结点的总数不是 k 的整数倍，请将最后剩余的结点保持原有顺序。要求不能只是单纯地改变结点内部的值，而是需要实际进行结点的交换。

例如，head=[1，2，3，4，5]， k =3，共分为两组，即[1，2，3]和[4，5]，前一组翻转为[3，2，1]，后一组结点的总数不是 k ，保持不变，这样翻转后head=[3，2，1，4，5]，如图2.24所示。

【限制】 链表中结点的数目为 n ，1≤ k ≤ n ≤5000，0≤Node.val≤1000。

进阶：设计一个只用 O （1）额外内存空间的算法解决此问题。

【解题思路】 k 个相邻结点作为一组+用头插法建表。为了方便，给单链表添加一个头结点h，用（pre，tail）表示一个翻转组，pre表示该翻转组首结点的前驱结点，tail表示该翻转组的尾结点， n 累计访问的结点的个数。初始时置pre为头结点，tail指向首结点， n =0。

当tail不为空时循环，如果++ n % k ==0成立，表示找到一个翻转组（pre，tail），此时将p设置为pre- next，即指向该翻转组的首结点，循环 k -1次，每次删除结点p之后的一个结点q，并且将结点q插入结点pre之后，例如 k =3时的翻转过程如图2.25所示。这样翻转一个翻转组后，结点p成为尾结点，同时结点作为下一个翻转组的pre继续进行类似的操作。最后返回h- next。

对应的算法如下。

C++：

提交运行：

Python：

提交运行： mpuw/zrQSF+Vwh4TCP+QxxmDgUwASmdzG20ptIGwuNPgdDlIcMaDTAPhIeOhOeqz