算法题学习 --- 链表内指定区间反转
描述
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)，空间复杂度 O(1)。 例如： 给出的链表为 NULL1→2→3→4→5→NULL, m=2,n=4m=2,n=4, 返回 1→4→3→2→5→NULL.
数据范围： 链表长度 0<size≤1000，0<m≤n≤size，链表中每个节点的值满足 0∣val∣≤1000
要求：时间复杂度 O(n) ，空间复杂度 O(n)
进阶：时间复杂度 O(n)，空间复杂度 O(1)
示例 1
示例 2
分析
考虑特殊情况
在进行问题分析过程前，我们先考虑一下特殊情况，那么在这道问题中，有哪些情况是特殊的呢？
不难发现，如下两种情况：
空链表，即头指针为 NULL，这种情况我们直接返回头指针即可；
链表只有一个节点，即 pHead->next 为 NULL，这种情况我们也直接返回头指针即可。
考虑一般情况
实际上我们可以将问题分解为几步：
找到第 m 个节点，记录前驱以及 m 节点；
将 m 到 n 之间视为子链表，进行链表反转，并记录最后的 n 节点及其后继节点；
最后将子链表与整体链表进行拼接：m 的前驱的 next 等于 n，m 的 next 等于 n 的后继
注意，这里还有一些细节问题，由于我们不确定头结点是否需要反转，我们可以申请一个虚拟节点，它的 next 指向头结点，这样，我们在返回信息时，只需要返回该虚拟节点的 next 节点即可，省去了许多问题分类判断。
代码演示
版本一
这里的实现方式就是上面的分析方式，注意在初始化时，我们将 pPre = pReturn;这点也是很重要的。
版本二
实际上我们只需要关注处理区间内的节点，在遍历处理区间内节点时，保持如下原则将 next 位置上面的节点不断移到最前面的位置即可
在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。
pCur：指向待反转区域的当前处理节点；
pNext：永远指向 pCur 的下一个节点，循环过程中，pCur 变化以后 pNext 会变化；
pPre：永远指向待反转区域的第一个节点的前驱，在循环过程中不变。
首先，我们通过遍历的方法找到了 m 位置的前一个节点 pPre,这里我们用例子中的{1,2,3,4,5},2,4 来举例，如下：
每次循环的任务都是将 pNext 位置的节点移到 pPre 后面
当前链表：pReturn-->1(pPre)-->2(pCur)-->3-->4-->5-->NULL
第一轮循环的任务是将 pNext 位置的 3 移到 pPre 后面
首先对 pNext 赋值为 pCur->next，
因为要移动 pNext，所以我们要先让 pCur 指向 pNext 的下一个位置，pCur->next = pNext->next
然后断开 pNext，此时 pNext 需要保存 pPre 的后续，pNext->next = pPre->next
最后将 pPre 的后继更新为 pNext。一次循环结束
此时链表变为 pReturn-->1(pPre)-->3(pNext)-->2(pCur)-->4-->5-->NULL
后面一轮的任务类似，是将 pNext(4)这个节点放到 pPre 的后面
版权声明: 本文为 InfoQ 作者【桑榆】的原创文章。
原文链接:【http://xie.infoq.cn/article/5066d80a910ae4b753b9a4751】。文章转载请联系作者。
北海虽赊，扶摇可接；东隅已逝，桑榆非晚！ 2020-02-29 加入
Android手机厂商-相机软件系统工程师 爬山/徒步/Coding
评论