【Java练习题第二期】：用Java实现链表内指定区域的反转

hi~本期是Java题目分享
小猪做了一个对于新手挺有挑战性的题目，题目难度中等，也很有意思，但也想了我好一会儿＞︿＜
索性就分享一下，希望对你们有帮助

文章目录

前言

本题是我本人自己的思考后所做，如果哪里有错误，请求大佬指出来（＾-＾）（＾-＾）！

题目：链表内指定区域反转

描述：
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。
例如：
给出的链表为 1\to 2 \to 3 \to 4 \to 5 \to NULL1→2→3→4→5→NULL, m=2,n=4m=2,n=4,
返回 1\to 4\to 3\to 2\to 5\to NULL1→4→3→2→5→NULL.

数据范围： 链表长度 0 < size \le 10000<size≤1000，0 < m \le n \le size0<m≤n≤size，链表中每个节点的值满足 |val| \le 1000∣val∣≤1000
要求：时间复杂度 O(n)O(n) ，空间复杂度 O(n)O(n)
进阶：时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)

图形解析

第一步：

为了让反转从头节点开始，可以在链表头加上一个虚拟节点当作第一个节点，head依旧是该虚拟节点的下一个节点，此时保证了第一个节点永远不会被反转。
图：

第二步：实现过程

第一次反转（动图）：

第二次反转（动图）：

有几次反转取决于n-m的值。

代码：

文字解析

（1）需要一个虚拟头节点
（2）使prev永远在m-1的位置不变
（3）cur在prev的下一个，还需要知道cur的下一个，也就是curNext
（4）反转主要目的是使得m位置的和m+1位置的互换，进行n-m次

那本期博客就到此结束了哈！

如果上面有不懂的可以私我哈，小猪永远在线！！
如果你觉得对你有帮助的或者写的可以的可以给小猪一个小小的三连鼓励一下小猪哦！谢谢啦！
别忘了关注小猪哦！小猪带你一起玩遍Java和嵌入式
那咱们下期再见啦！