牛客网高频算法题系列-BM2-链表内指定区间反转

题目描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)，空间复杂度 O(1)。

原题目见：BM2 链表内指定区间反转

解法一：链表遍历，指针交换

因为起始位置可能是头结点，所以首先设置一个虚拟的头结点dummyNode并将next指向原有的头结点，然后处理过程如下：

• 首先遍历链表，找到起始位置m的前一个结点pre，用来记录反转前的结点；

• 然后用cur和next记录pre的next结点，用next记录cur的next结点；

• 然后继续遍历链表，通过交换pre、next、cur的next指针，将next结点转到pre结点的下一个结点处，然后循环处理cur的下一个结点；

• 遍历到结束结束位置n的结点即反转结束。

• 最后，返回dummyNode结点的next结点即为反转后的链表。

1.01^{365} ≈ 37.7834343329   

0.99^{365} ≈ 0.02551796445   

相信坚持的力量！