链表内指定区间反转

首先处理特殊情况：若 m 和 n 相等无需反转，直接返回原链表。然后用一个虚拟头节点dummy简化头节点的处理，先找到反转区间的前驱节点，再定位到反转区间的起始节点cur。
然后进行局部反转，循环将节点之间的链接断开并反向连接，逐步推进指针完成 m 到 n 区间的反转。反转完成后，需要将反转区间的首尾与原链表重新连接。
以下是对应的代码：
class Solution {public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (m == n) return head; 
        
        ListNode dummy(0); 
        dummy.next = head;
        ListNode* pre = &dummy;
        ListNode* t = pre;       
        // 找到反转区间的前驱节点
        for (int i = 1; i < m; ++i) {
            t = t->next;
        }
        ListNode* cur = t->next; // 反转区间的起始节点
        ListNode* next = cur->next; // 记录原链表的后继
        ListNode* NU = nullptr;         
        // 局部反转m到n的区间
        for (int i = m; i < n; ++i) {
            cur->next = NU; 
            NU = cur;         //断开链接
            pre = cur;        
            cur = next;       // 推进当前节点
            next = cur->next; // 记录下一个节点
            cur->next = pre;  // 完成当前步反转
        }
        
        // 重新连接反转区间的首尾
        t->next->next = next; 
        t->next = cur;                
        return dummy.next;  }};

该代码的时间复杂度为 O (n)，空间复杂度为 O (1)