链表内指定区间反转

题目：

将一个节点数为 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和需要翻转的head
        rTail = 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;
}

运行结果：