算法题学习 --- 链表中的节点每 k 个一组
题目
描述
将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表 如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样 你不能更改节点中的值，只能更改节点本身。
数据范围： 0≤n≤2000 ，1≤k≤2000 ，链表中每个元素都满足 0≤val≤1000 要求空间复杂度 O(1)，时间复杂度 O(n)
例如：
给定的链表是 1→2→3→4→5
对于 k = 2 , 你应该返回 2→1→4→3→5
对于 k = 3 , 你应该返回 3→2→1→4→5
示例 1
示例 2
分析
考虑特殊情况
在进行问题分析过程前，我们先考虑一下特殊情况，那么在这道问题中，有哪些情况是特殊的呢？
不难发现，如下两种情况：
空链表，即头指针为 NULL，这种情况我们直接返回头指针即可；
链表只有一个节点，即 pHead->next 为 NULL，这种情况我们也直接返回头指针即可。
如果 k<=1，说明并不需要进行链表反转，直接返回头指针即可
考虑一般情况
这里我们看一下问题的一般形式，也即是对中间的每一组链表进行逆序，这个的方法其实在我们之前的问题中已经出现过了https://xie.infoq.cn/article/5066d80a910ae4b753b9a4751 ，所以这里我们就将问题做一下拆解：
找出当前需要进行逆序的子链表，确定该子链表的 pPre 和 pEnd;
对 pPre 到 pEnd 中间的节点进行区间逆序算法；
更新 pPre 和 pEnd 到下一个子链表，直到无法找到满足条件的子链表。
注意，这里我们也同样使用一个虚拟 node 来指向我们的头结点，避免对头结点做判断导致的逻辑复杂。
代码示例
注意：如下的代码示例中
pReturn 是我们的返回节点，它指向头结点；
pPre 是每一个子链表的头结点的前驱节点，开始时初始化为 pReturn，完成子链表逆序之后被更新为 pCur 的值，在子链表逆序过程中不发生改变；
pCur 是子链表中当前指向的节点，在逆序完成后（即 pNext 节点被插入 pPre 后面之后）指向下一个子链表的第一个元素，也即是下一个子链表头节点的前驱节点；
pNext 是 pCur 的下一个元素，如果不等于 pEnd，那就需要逆序插入到 pPre 后面；
pEnd 是子链表的尾节点。
还有一点，如果我们在寻找 pEnd 节点的过程中遍历到了链表末尾，那说明最后的这一组不需要做子链表逆序，直接返回 pReturn->next 即可。
版权声明: 本文为 InfoQ 作者【桑榆】的原创文章。
原文链接:【http://xie.infoq.cn/article/b0a7871cf0c749ee8da53cc56】。文章转载请联系作者。
北海虽赊，扶摇可接；东隅已逝，桑榆非晚！ 2020-02-29 加入
Android手机厂商-相机软件系统工程师 爬山/徒步/Coding
评论