链表内指定区间反转

问题

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)，空间复杂度 O(1)。

思路

1. 采用双指针移动到指定位置： pre 移动到挪动区间的起始位置的前一个位置，cur 移动到挪动区间的起始位置。
2. 连接 cur 与 cur 的下下个元素，断开 cur 与 next 的连接；next 连接到 pre 后一元素之前；pre 指向 next。

代码实现

/** * struct ListNode { * int val; * struct ListNode *next; * }; */

class Solution {
    
public:
    /** * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
    
        // write code here
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* pre = dummyHead;
        // 0 < m < size,所以本题链表下标从 1 开始，pre 指向翻转区间的起始前一个位置
        for (int i = 1; i < m; i++)
        {
    
            pre = pre->next;
        }
        ListNode* cur = pre->next;
        
        for (int i = m; i < n; i++)
        {
    
            ListNode* next = cur->next;
            // 断开 cur 与 next 的连接
            cur->next = next->next;
            // 将后续的 next 移动到 pre 下一个元素前
            next->next = pre->next;
            // 连接 pre 和 next
            pre->next = next;
        }
        
        return dummyHead->next;
    }
};