NC21 链表内指定区间反转（链表）

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

反转局部链表，可以将该局部部分当作完整链表进行反转
再将已经反转好的局部链表与其他节点建立连接，重构链表
使用虚拟头节点的技巧，可以避免对头节点复杂的分类考虑，简化操作。

class Solution {
public:

    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* dummy = new ListNode(0);//设置虚拟头节点
        ListNode* pre = dummy;
        dummy->next=head;
        //走left-1步到left的前一个节点
        for(int i=0;inext;
        }
        //走roght-left+1步到right节点
        ListNode* right=pre;
        for(int i=0;inext;
        }
        //截取出一个子链表
        ListNode* left=pre->next;
        ListNode* cur=right->next;
        //切断链接
        pre->next=nullptr;
        right->next=nullptr;
        //反转局部链表
        reverse(left);
        //接回原来的链表
        pre->next=right;
        left->next=cur;
        return dummy->next;
    }
    ListNode* reverse(ListNode* head){
        ListNode* pre=new ListNode(0);
        ListNode* cur=head;
        ListNode* next=nullptr;
        while(cur!=nullptr){
            next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
};