网站推荐货源廊坊seo推广公司

题目：

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

数据范围： 链表长度 0< size ≤1000，0<m≤n≤size，链表中每个节点的值满足∣val∣≤1000

要求：时间复杂度O(n) ，空间复杂度O(n)

进阶：时间复杂度O(n)，空间复杂度O(1)

示例1：

输入：{1,2,3,4,5},2,4返回值：{1,4,3,2,5}

示例2：

输入：{5},1,1返回值：{5}

解题思路：

这个是在 《单向链表翻转》基础上增加了些难度，指定了区间内的翻转。

首先考虑链表的有效性和m、n 的值合法性；

接着，考虑m 的值，m 可能为1，则要求链表从头开始翻转；

如果m 不为0，那就是将量表分为 3 节，头、中、尾三部分。

代码：

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类*/
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {if (m >= n || NULL == head)return head;struct ListNode* rHead = head;struct ListNode* rTail = NULL;for (int i = 1; NULL != head && i < m; ++i) { //找到rTail和需要翻转的headrTail = head;head = head->next;}if (NULL == rTail) { //第一个就需要翻转rHead = NULL;rTail = NULL;}struct ListNode* mHead = NULL;struct ListNode* mTail = NULL;struct ListNode* mp = NULL;for (int i = m; NULL != head && i <= n; ++i) { //进行翻转mp = head;head = head->next;mp->next = mHead;mHead = mp;if (NULL == mTail) {mTail = mp;}}if (NULL != rTail) { //拼接m之前的连接rTail->next = mHead;}if (NULL != mTail) { //拼接n后面的链表mTail->next = head;}if (NULL == rHead) { //如果从第一个开始翻转rHead = mHead;}return rHead;
}

运行结果：

 

是否还有好的方法，请大神们不吝赐教！！！