题解 | #链表内指定区间反转#

#include <cstdio>
class Solution {
public:
	时间复杂度On  空间复杂度O1
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* q = head;
        ListNode* p = head;
        for(int i = 1; i < m - 1; i ++) p = p->next;  //令p指向m所指向的节点的前一个节点
        for(int i = 1; i < n; i ++) q = q->next;  //q指向n所指向的节点
        if(m == 1) {  //目的仍然是让p指向m所指的节点的前一个结点
            p = new ListNode(-1);
            p->next = head;
        }
        int cnt = n - m;  //循环cnt次
        while(cnt --) {  //依次把要翻转的区间内的节点往后放
            ListNode* temp = p->next;
            p->next = temp->next;  
            temp->next = q->next;
            q->next = temp;
        }
        if(m == 1) return p->next;  //针对特殊情况
        else return head;
    }
};