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

首先创建一个哑结点，方便后续操作。

找到指定区间的第一个的前一个结点。

进行n-m+1次反转链表的操作就行了。

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if (!head || m == n)return head;
        ListNode dummy(0);
        dummy.next = head;
        ListNode *pre = &dummy;
        //找到反转部分的前一个（后续需要重新连接，需要知道该结点位置）
        for (int i = 1; i < m; ++i)pre = pre->next;

        ListNode *curr = pre->next;
        ListNode *start = curr;//记下反转部分的第一个，反转之后需要指向第一个非反转结点
        ListNode *prev = nullptr;
        ListNode *tmp;

        int k = n - m + 1;
        for (int i = 0; i < k; ++i) {
            tmp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = tmp;
        }
	  //操作结束后，prev是反转后的开头，curr是反转部分的下一个结点
        pre->next = prev;
        start->next = curr;
        return dummy.next;
    }
};

};